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)严格约束的证据版本。