Tata Institute of Fundamental Research
Hardness of Approximation via a Variant of Equivalence of Optimization and Separation Problem
STCS Student Seminar
Speaker:
Gunjan Kumar
Date:
Friday, 16 Aug 2019, 17:15 to 18:45
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: The equivalence of optimization and separation is a widely used tool. The reduction from optimization to separation is particularly useful for, e.g., solving linear programs with exponential constraints. There are many variants of this equivalence, one such is the equivalence of weak validity and weak membership. We use this equivalence to show a hardness of approximation for Coverage Norm Extension problem.
In this problem, we are given $n$ points and a partial function value at these points. The goal is to find the minimum L_1 distance of the partial function from a coverage function. If F denotes the sum of the values of partia function values then clearly an additive F-approximatio algorithm exist. We show that it is NP-hard to approximate with a quantity sublinear in F.
This is a joint work with Umang Bhaskar.
| Speaker: | Gunjan Kumar |
| Date: | Friday, 16 Aug 2019, 17:15 to 18:45 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: The equivalence of optimization and separation is a widely used tool. The reduction from optimization to separation is particularly useful for, e.g., solving linear programs with exponential constraints. There are many variants of this equivalence, one such is the equivalence of weak validity and weak membership. We use this equivalence to show a hardness of approximation for Coverage Norm Extension problem.
In this problem, we are given $n$ points and a partial function value at these points. The goal is to find the minimum L_1 distance of the partial function from a coverage function. If F denotes the sum of the values of partia function values then clearly an additive F-approximatio algorithm exist. We show that it is NP-hard to approximate with a quantity sublinear in F.
This is a joint work with Umang Bhaskar.
In this problem, we are given $n$ points and a partial function value at these points. The goal is to find the minimum L_1 distance of the partial function from a coverage function. If F denotes the sum of the values of partia function values then clearly an additive F-approximatio algorithm exist. We show that it is NP-hard to approximate with a quantity sublinear in F.
This is a joint work with Umang Bhaskar.