Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{UniqueCoverage_SODA2006,
  AUTHOR        = {Erik D. Demaine and Uriel Feige and MohammadTaghi Hajiaghayi
                   and Mohammad R. Salavatipour},
  TITLE         = {Combination Can Be Hard: Approximability of the Unique
                   Coverage Problem},
  BOOKTITLE     = {Proceedings of the 17th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2006)},
  bookurl       = {http://www.siam.org/meetings/da06/},
  ADDRESS       = {Miami, Florida},
  MONTH         = {January 22--24},
  YEAR          = 2006,
  PAGES         = {162--171},

  withstudent   = 1,
  papers        = {UniqueCoverage_SICOMP},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineHFS06},
  ee            = {https://dl.acm.org/doi/10.5555/1109557.1109577},
  comments      = {This paper is also available from <A HREF="https://dl.acm.org/doi/10.5555/1109557.1109577">ACM</A>.},
}

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.

Comments:

This paper is also available from ACM.

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)