Combination Can Be Hard: Approximability of the Unique Coverage Problem

DOI10.1137/060656048zbMath1192.68353OpenAlexW2010916800MaRDI QIDQ3395040

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

Publication date: 20 August 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060656048

zbMATH Keywords

wireless networkshardness of approximationunique coverage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (23)

Minimum ply covering of points with disks and squares ⋮ The parameterized complexity of unique coverage and its variants ⋮ Unique Covering Problems with Geometric Sets ⋮ Minimum ply covering of points with unit squares ⋮ The Stackelberg minimum spanning tree game ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ Stackelberg network pricing games ⋮ Unnamed Item ⋮ Optimal deterministic broadcasting in known topology radio networks ⋮ On the complexity of a bundle pricing problem ⋮ Unique Coverage with Rectangular Regions ⋮ Approximating the revenue maximization problem with sharp demands ⋮ On nonlinear multi-covering problems ⋮ On stackelberg pricing with computationally bounded customers ⋮ A 4.31-approximation for the geometric unique coverage problem on unit disks ⋮ The checkpoint problem ⋮ On fair price discrimination in multi-unit markets ⋮ Stackelberg network pricing is hard to approximate ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ On social envy-freeness in multi-unit markets ⋮ Exact multi-covering problems with geometric sets ⋮ Nearly Optimal NP-Hardness of Unique Coverage ⋮ Geometric red-blue set cover for unit squares and related problems

This page was built for publication: Combination Can Be Hard: Approximability of the Unique Coverage Problem