**Reference**:- 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. **Abstract**:-
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(2^{nε}) for some ε > 0. We also prove*O*(1/log^{1/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. **Availability**:- 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.

Last updated May 28, 2024 by Erik Demaine.