Restricted parameter range promise set cover problems are easy

Abstract

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.

Keywords

Set cover problem / lattice / closest vector problem (CVP) / shortest vector problem (SVP)

References

[1] Ajtai M. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Proc STOC 1998. 1998, 10−19

[2] Arora S, Babai L, Stern J, Sweedyk Z. The hardness of approximating optima in lattices, codes and systems of linear equations. J Comput System Sci, 1997, 54(2): 317−331

[3] Bansal N, Khot S. Inapproximability of hypergraph vertex cover and applications to scheduling problems. Preprint, 2009

[4] Bellare M, Goldwasser S, Lund C, Russell A. Efficient multi-prover interactive proofs with applications to approximation problems. In: Proc STOC 1993. 1993, 113−131

[5] Chvatal V. A greedy heuristic for the set-covering problem. Math Oper Res, 1979, 4: 233−235

[6] Dinur I, Guruswami V, Khot S, Regev O. A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J Comput, 2005, 34(5): 1129−1146

[7] Dinur I, Kindler G, Raz R, Safra S. An improved lower bound for approximating CVP. Combinatorica, 2003, 23(2): 205−243

[8] Dumer I, Micciancio D, Sudan M. Hardness of approximating the minimum distance of a linear code. IEEE Trans Inform Theory, 2003, 49(1): 22−37

[9] Feige U. A threshold of ln n for approximating set cover. J ACM, 1998, 45(4): 634−652

[10] Haviv I, Regev O. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Proc STOC 2007. 2007, 469−477

[11] Hochbaum D. Approximation algorithms for set covering and vertex cover problems. SIAM J Comput, 1982, 11: 555−556

[12] Johnson D S. Approximation algorithms for combinatorial problems. J Comput System Sci, 1974, 9: 256−278

[13] Khot S. Hardness of approximating the shortest vector problem in lattices. J ACM, 2005, 52(5): 789−808

[14] Khot S, Regev O. Vertex cover might be hard to approximate to within 2−ε. In: Proc 18th IEEE Annual Conference on Computational Complexity. Los Alamitos: IEEE Computer Society Press, 2003, 379−386

[15] Lovasz L. On the ratio of optimal integral and fractional covers. Discrete Math, 1975, 13: 383−390

[16] Lund C, Yannakakis M. Hardness of approximating minimization problem. J ACM, 1994, 41(5): 960−981

[17] Micciancio D. The shortest vector problem is NP-hard to approximate within some constant. SIAM J Comput, 2001, 30(6): 2008−2035

[18] Micciancio D, Goldwasser S. Complexity of Lattice Problems: A Cryptographic Perspective. Dordrecht: Kluwer Academic Publishers, 2002

[19] Raz R, Safra S. A sub-constant error-probability low degree test and a sub-constant error-probability PCP characteristic of NP. In: Proc STOC 1997. 1997, 475−484

[20] Trevisan L. Non-approximability results for optimization problems on bounded degree instances. In: Proc STOC 2001. 2001, 453−461

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg