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.

Key words： 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