Restricted parameter range promise set cover problems are easy
- 时间:0
- 分类:O22[理学—运筹学与控制论;理学—数学] TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
- 作者机构:[1]Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China
- 相关基金:Acknowledgements This work was supported by the National Natural Science Foundation of China (Grant No. 11371138).
中文摘要:
限制参数范围集合盖子问题是有参数的限制范围的 NP 难的集合盖子问题的一种弱形式。我们由格子为这个问题给一个多项式时间算法。
英文摘要:
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.