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
Last updated December 1, 2021 by