Nearly optimal NP-hardness of unique coverage
From MaRDI portal
Publication:5269824
DOI10.1137/16M1070682zbMATH Open1371.68098OpenAlexW2625369867MaRDI QIDQ5269824FDOQ5269824
Venkatesan Guruswami, Euiwoong Lee
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- On the hardness of approximating minimization problems
- Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
- Combination Can Be Hard: Approximability of the Unique Coverage Problem
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Title not available (Why is that?)
- Nearly Optimal NP-Hardness of Unique Coverage
Cited In (3)
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)
