Nearly optimal NP-hardness of unique coverage

DOI10.1137/16M1070682MaRDI QIDQ5269824zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 28 June 2017

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

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

zbMATH Keywords

hardness of approximationunique coverage1-in-\(k\) hitting set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Nearly optimal NP-hardness of unique coverage
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• scientific article; zbMATH DE number 1670858
• Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
• A threshold of ln n for approximating set cover

Cites work

• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Improved hardness results for profit maximization pricing problems with unlimited supply
• Nearly optimal NP-hardness of unique coverage
• On the hardness of approximating minimization problems
• On the power of unique 2-prover 1-round games
• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set

Cited in

(7)

• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• The parameterized complexity of unique coverage and its variants
• Nearly optimal NP-hardness of unique coverage
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Nearly optimal NP-hardness of unique coverage
• Maximum unique coverage on streams: improved FPT approximation scheme and tighter space lower bound

This page was built for publication: Nearly optimal NP-hardness of unique coverage

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