Portal de Periódicos da CAPES

Combination Can Be Hard: Approximability of the Unique Coverage Problem

2008; Society for Industrial and Applied Mathematics; Volume: 38; Issue: 4 Linguagem: Inglês

10.1137/060656048

1095-7111

Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour,

Cryptography and Data Security

We prove semilogarithmic 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 $\mathrm{NP}\not\subseteq\operatorname{BPTIME}(2^{n^\varepsilon})$ for an arbitrary $\varepsilon>0$, we prove $O(1/\log^{\sigma}n)$ inapproximability for some constant $\sigma=\sigma(\varepsilon)$. We also prove $O(1/\log^{1/3-\varepsilon}n)$ inapproximability for any $\varepsilon>0$, assuming that refuting random instances of 3SAT is hard on average; and we prove $O(1/\log n)$ inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish an $\Omega(1/\log n)$-approximation algorithm, even for a more general (budgeted) setting, and obtain an $\Omega(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.