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

hardness of approximationunique coveragewireless networks

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

(31)

• Optimal deterministic broadcasting in known topology radio networks
• On fair price discrimination in multi-unit markets
• Exact multi-covering problems with geometric sets
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• On social envy-freeness in multi-unit markets
• Geometric red-blue set cover for unit squares and related problems
• The parameterized complexity of unique coverage and its variants
• Stackelberg network pricing games
• Stackelberg network pricing is hard to approximate
• Unique covering problems with geometric sets
• Nearly optimal NP-hardness of unique coverage
• Unique coverage with rectangular regions
• On Stackelberg pricing with computationally bounded customers
• Pricing problems with buyer preselection
• Approximating the revenue maximization problem with sharp demands
• On nonlinear multi-covering problems
• Nearly optimal NP-hardness of unique coverage
• The Parameterized Complexity of the Unique Coverage Problem
• Local search strikes again: PTAS for variants of geometric covering and packing
• Minimum ply covering of points with unit squares
• The Stackelberg minimum spanning tree game
• Reception capacity: definitions, game theory and hardness
• On the complexity of a bundle pricing problem
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Minimum membership geometric set cover in the continuous setting
• Maximum unique coverage on streams: improved FPT approximation scheme and tighter space lower bound
• Sublogarithmic approximation for tollbooth pricing on a cactus
• The checkpoint problem
• Maximum coverage in the data stream model: parameterized and generalized
• Minimum ply covering of points with disks and squares
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

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)