Restricted parameter range promise set cover problems are easy

Restricted parameter range promise set cover problems are easy

导出

摘要 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. 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.

作者 Hao CHEN

机构地区 Department of Mathematics

出处《Frontiers of Mathematics in China》 SCIE CSCD 2014年第6期1253-1260,共8页 中国高等学校学术文摘·数学（英文）

基金 Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant No. 11371138）.

关键词 Set cover problem LATTICE closest vector problem （CVP） shortestvector problem （SVP） Set cover problem, lattice, closest vector problem （CVP）, shortestvector problem （SVP）

分类号 O22 [理学—运筹学与控制论] TP301.6 [自动化与计算机技术—计算机系统结构]

引文网络
相关文献

参考文献20

1Ajtai M. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Proc STOC 1998. 1998, 10 -19.
2Arora 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.
3Bansal N, Khot S. Inapproximability of hypergraph vertex cover and applications to scheduling problems. Preprint, 2009, http://cs.nyu.edu/khot/publications.html.
4Bellare M, Goldwasser S, Lund C, Russell A. Efficient multi-prover interactive proofs with applications to approximation problems. In: Proc STOC 1993. 1993, 113-131.
5Chvatal V. A greedy heuristic for the set-covering problem. Math Oper Res, 1979, 4: 233-235.
6Dinur 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.
7Dinur I, Kindler C, Raz R, Safra S. An improved lower bound for approximating CVP. Combinatorica, 2003, 23(2): 205-243.
8Dumer I, Micciancio D, Sudan M. Hardness of approximating the minimum distance of a linear code. IEEE Trans Inform Theory, 2003, 49(1): 22-37.
9Haviv I, Regev O. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Proc STOC 2007. 2007, 469-477.
10Hochbaum D. Approximation algorithms for set covering and vertex cover problems. SIAM J Comput, 1982, ii: 555 556.

1宋萌萌,尚海锋.具测度初值的非线性抛物方程组的Cauchy问题[J].山东大学学报（理学版）,2016,51(10):41-47.
2孙志永.基于51单片机恒温控制系统的设计[J].中国科技博览,2016,0(3):142-142.
3吴东生,吴明.检测站计量认证检验项目和限制范围[J].汽车维护与修理,2009(7):51-53.
4Khac Duc Do,Dang Binh Nguyen,Anh Duc Nguyen.Control of Nonlinear Systems with Output Tracking Error Constraints[J].Journal of Measurement Science and Instrumentation,2010,1(3):217-223. 被引量：1
5Gleb Arsentevich Abakumov Victor Borisovich Fedoseev.Criteria of Nonextensive Behaviour of System in Conditions of External Fields[J].材料科学与工程（中英文A版）,2012,2(11):747-752.
6A.BALLESTER-BOLINCHES,Luis M.EZQUERRO,Alexander N.SKIBA.Local Embeddings of Some Families of Subgroups of Finite Groups[J].Acta Mathematica Sinica,English Series,2009,25(6):869-882. 被引量：16
7Vitor H. Fernandes Jintana Sanwong.On the Ranks of Semigroups of Transformations on a Finite Set with Restricted Range[J].Algebra Colloquium,2014,21(3):497-510. 被引量：6
8满堂喝彩.给音频文件开刀 Absolute MP3 Splitter[J].电脑迷,2005,0(10):59-59.
9张玲玲.限制范围的广义多项式插值[J].山西大学学报（自然科学版）,1992,15(4):351-355.
10Rene Rossi,Mohammad A.S. Masoum.A Practical Approach Based on Equal Area Criteria for Stability Analysis of Weak Networks with Wind Generation Penetration[J].Journal of Energy and Power Engineering,2012,6(4):629-637.

Frontiers of Mathematics in China

2014年第6期

浏览历史

内容加载中请稍等...

Restricted parameter range promise set cover problems are easy

参考文献20

相关作者

相关机构

相关主题

浏览历史