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
- 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
Last updated June 1, 2023 by