Combination Can Be Hard: Approximability of the Unique Coverage Problem

DOI10.1137/060656048zbMATH Open1192.68353OpenAlexW2010916800MaRDI QIDQ3395040FDOQ3395040

Authors: Erik D. Demaine, Mohammad Salavatipour, Mohammad T. Hajiaghayi, Uriel Feige 

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

Recommendations

• Nearly optimal NP-hardness of unique coverage
• Nearly optimal NP-hardness of unique coverage
• The budgeted maximum coverage problem
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• A threshold of ln n for approximating set cover

zbMATH Keywords

wireless networkshardness of approximationunique coverage

Mathematics Subject Classification ID

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

Cited In (27)

• Minimum ply covering of points with disks and squares
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• The Stackelberg minimum spanning tree game
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• The parameterized complexity of unique coverage and its variants
• Nearly optimal NP-hardness of unique coverage
• Pricing problems with buyer preselection
• Optimal deterministic broadcasting in known topology radio networks
• Minimum ply covering of points with unit squares
• On Stackelberg pricing with computationally bounded customers
• Local search strikes again: PTAS for variants of geometric covering and packing
• On fair price discrimination in multi-unit markets
• Nearly optimal NP-hardness of unique coverage
• Stackelberg network pricing games
• On social envy-freeness in multi-unit markets
• Unique coverage with rectangular regions
• Unique covering problems with geometric sets
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Stackelberg network pricing is hard to approximate
• The checkpoint problem
• Exact multi-covering problems with geometric sets
• Approximating the revenue maximization problem with sharp demands
• The Parameterized Complexity of the Unique Coverage Problem
• On the complexity of a bundle pricing problem
• On nonlinear multi-covering problems
• Reception capacity: definitions, game theory and hardness
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3395040)