Restricted parameter range promise set cover problems are easy

DOI10.1007/s11464-014-0429-8zbMath1314.68152arXiv1110.1896OpenAlexW2103937176MaRDI QIDQ2258109

Hao Chen

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

zbMATH Keywords

latticeset cover problemclosest vector problem (CVP)shortest vector problem (SVP)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

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