COMBINATION CAN BE HARD: APPROXIMABILITY OF THE UNIQUE COVERAGE PROBLEM
We prove semilogarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, assuming that NP not subset of BPTIME(2(n epsilon)) for an arbitrary e > 0, we prove O(1/log(sigma) n) inapproximability for some constant sigma = sigma(epsilon). We also prove O(1/log(1/3-epsilon) n) inapproximability for any e > 0, assuming that refuting random instances of 3SAT is hard on average; and we prove O(1/log(sigma) n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish an Omega(1/log n)-approximation algorithm, even for a more general (budgeted) setting, and obtain an Omega(1/log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems, including max cut, maximum coverage, and radio broadcasting.
unique coverage hardness of approximation wireless networks