It is well-known that an algorithm exists which approximates the NP-complete problem of Set Cover within a factor of ln(n), and it was recently proven that this approximation ratio is optimal unless P = NP. This optimality result is the product of many advances in characterizations of NP, in terms of interactive proof systems and probabilistically checkable proofs (PCP), and improvements to the analyses thereof. However, as a result, it is difficult to extract the development of Set Cover approximation bounds from the greater scope of proof system analysis. This paper attempts to present a chronological progression of results on lower-bounding the approximation ratio of Set Cover. We analyze a series of proofs of progressively better bounds and unify the results under similar terminologies and frameworks to provide an accurate comparison of proof techniques and their results. We also treat many preliminary results as black-boxes to better focus our analysis on the core reductions to Set Cover instances. The result is alternative versions of several hardness proofs, beginning with initial inapproximability results and culminating in a version of the proof that ln(n) is a tight lower bound.


翻译:众所周知,目前存在着一种算法,这种算法在内(n)系数范围内接近NP-完整的“Set Cover”问题,而且最近证明,除非P=NP,这种近似比率是最佳的。这种最佳性是NP定性的许多进步的产物,这些进步包括互动验证系统和概率可核实的证明,以及对其分析的改进。然而,因此,很难从更大的验证系统分析范围中提取出“Set Cover Cover Cover”近似界限的开发。本文试图提出“Set Cover”下限近似比率结果的逐年进展。我们分析一系列逐步改善界限的证据,并将类似术语和框架下的结果统一起来,以提供对证据技术及其结果的准确比较。我们还将许多初步结果作为黑箱,以便更好地将我们的分析重点放在“Set Cover”实例的核心削减上。结果为几种硬性证据的替代版本,首先是初步的不兼容性结果,最后是内部(n)严格约束的证据版本。

0
下载
关闭预览

相关内容

专知会员服务
36+阅读 · 2021年7月17日
专知会员服务
81+阅读 · 2021年5月10日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年1月29日
Arxiv
0+阅读 · 2022年1月29日
VIP会员
相关资讯
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员