Nearly Optimal NP-Hardness of Unique Coverage

DOI10.1137/16M1070682zbMath1371.68098OpenAlexW2625369867MaRDI QIDQ5269824

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)

Related Items (1)

Nearly Optimal NP-Hardness of Unique Coverage

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold of ln n for approximating set cover
• Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Relations between average case complexity and approximation complexity
• On the power of unique 2-prover 1-round games
• On the hardness of approximating minimization problems
• Nearly Optimal NP-Hardness of Unique Coverage
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

This page was built for publication: Nearly Optimal NP-Hardness of Unique Coverage