Restricted parameter range promise set cover problems are easy
From MaRDI portal
Publication:2258109
DOI10.1007/s11464-014-0429-8zbMath1314.68152arXiv1110.1896OpenAlexW2103937176MaRDI QIDQ2258109
Publication date: 2 March 2015
Published in: Frontiers of Mathematics in China (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.1896
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- A threshold of ln n for approximating set cover
- Hardness of approximating the shortest vector problem in lattices
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- On the hardness of approximating minimization problems
- Hardness of approximating the minimum distance of a linear code
- Non-approximability results for optimization problems on bounded degree instances
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover