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”, SIAM Journal on Computing, volume 38, number 4, September 2008, pages 1464–1483.

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, assuming that NP ⊈ BPTIME(2nε) for an arbitrary ε > 0, we prove O(1/logσ n) inapproximability for some constant σ = σ(ε). 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 an Ω(1/log n)-approximation algorithm, even for a more general (budgeted) setting, and obtain 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.

This paper is also available from SIAM.

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

Related papers:
UniqueCoverage_SODA2006 (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 July 25, 2017 by Erik Demaine.