Paper by Erik D. Demaine

Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour, “Combination Can Be Hard: Approximability of the Unique Coverage Problem”, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 162–171.

We prove semi-logarithmic 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, we prove O(1/logσ(ε) n) inapproximability assuming that NP ⊈ BPTIME(2nε) for some ε > 0. We also prove O(1/log1/3−ε n) inapproximability, for any ε > 0, assuming that refuting random instances of 3SAT is hard on average; and prove O(1/log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Ω(1/log n)-approximation algorithm as well as an Ω(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.

The paper is available in PostScript (365k), gzipped PostScript (139k), and PDF (203k).
See information on file formats.
[Google Scholar search]

Related papers:
UniqueCoverage_SICOMP (Combination Can Be Hard: Approximability of the Unique Coverage Problem)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 28, 2024 by Erik Demaine.