Approximability of the Unique Coverage Problem

In this talk, we consider a natural maximization version of the well-known set cover problem, called unique coverage: given a collection of sets, find a sub-collection that maximizes the number of elements covered exactly once. This problem, which is motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broadcasting. We prove sub-logarithmic hardness results for unique coverage. Specifically, we prove Ω(log^σ(ε) n) inapproximability assuming that NP not ⊆ BPTIME (2^{n^ε}) for some ε > 0. We also prove Ω(log^1/3-ε n) inapproximability, for any ε > 0, assuming that refuting random instances of 3SAT is hard on average; and prove Ω(log n) inapproximability under a plausible hypothesis. We establish easy logarithmic upper bounds even for a more general (budgeted) setting, giving an O (log B) approximation algorithm when every set has at most B elements. Our hardness results have other implications regarding the hardness of some well-studied problems in computational economics. In particular, for the problem of unlimited-supply single-minded (envy-free) pricing, a recent result by Guruswami et al. [SODA’05] proves an O (log n) approximation, but no inapproximability result better than APX-hardness is known. Our hardness results for the unique coverage problem imply the same hardness of approximation bounds for this version of envy-free pricing.

Joint work with: E. Demaine, U. Feige, and M. Hajiaghayi.