Approximability of the Unique Coverage Problem

Опубликовано 8 сентября 2016, 0:59

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 $\Omega(\log^{\sigma(\epsilon)} n)$ inapproximability assuming that $\NP \not\subseteq \BPTIME(2^{n^\eps})$ for some $\epsilon > 0$. We also prove $\Omega(\log^{1/3-\epsilon} n)$ inapproximability, for any $\epsilon > 0$, assuming that refuting random instances of 3SAT is hard on average; and prove $\Omega(\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.