Hardness of Approximation via a Variant of Equivalence of Optimization and Separation Problem

Gunjan Kumar
Friday, 16 Aug 2019, 17:15 to 18:45
A-201 (STCS Seminar Room)
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.