Combination Can Be Hard: Approximability of the Unique Coverage Problem

DOI10.1137/060656048MaRDI QIDQ3395040zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

wireless networkshardness of approximationunique coverage

Mathematics Subject Classification ID

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

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

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
• On fair price discrimination in multi-unit markets
• Local search strikes again: PTAS for variants of geometric covering and packing
• 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
• Stackelberg network pricing is hard to approximate
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• The checkpoint problem
• Approximating the revenue maximization problem with sharp demands
• Exact multi-covering problems with geometric sets
• On the complexity of a bundle pricing problem
• The Parameterized Complexity of the Unique Coverage 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)