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.
