Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics
复制标题
约翰逊覆盖假设：ℓp 度量中 k 均值和 k 中位数的不近似性
DOI：
10.1137/1.9781611977073.63
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Euiwoong Lee
中科院分区：
文献类型：
--
作者：
Vincent Cohen;Karthik C. S.;Euiwoong Lee
K-中值和K-均值是聚类算法最常用的两个目标。尽管付出了大量的努力，但对这些目标的可近似性的良好理解，特别是在ℓp度量中，仍然是一个主要的悬而未决的问题。在这篇文章中，我们显著地改进了文献中已知的ℓp-度量中这些目标的逼近因子的难度，我们引入了一个新的假设，称为Johnson覆盖假说(JCH)，该假说大致地断言，即使当集合系统的隶属图是Johnson图的子图时，已被广泛研究的集合系统上的Maxk覆盖问题也很难逼近到大于(1-1/e)的因子。然后，我们证明了与Cohen-Addad和Karthik(FOCS‘19)所介绍的嵌入技术的推广一起，JCH暗示了ℓp-度量中的叉中值和k-均值对于接近于一般度量所得到的因子的逼近结果的硬度。特别地，假设JCH，我们证明了很难近似k-均值目标：离散情况：在ℓ1-度量中的因子为3.94，在ℓ2-度量中的因子为1.73；这比先前在唯一博弈猜想下得到的因子1.56和1.17有所改进。连续的情况：在ℓ1-度量中的因子为2.10，在ℓ2-度量中的因子为1.36；这改进了之前在UGC下得到的ℓ2-度量的因子1.07(据我们所知，在ℓ1-度量中K-均值的连续情况以前没有在文献中被分析过)。我们也在k-中值目标下得到了类似的改进。此外，我们使用Dinur等人的工作证明了JCH的一个弱版本。(SICOMP‘05)，并将Cohen-Addad和Karthik(FOCS’19)的所有结果恢复到(几乎)相同的不可逼近因子，但现在是在标准的NP≠P假设下(而不是UGC)。最后，我们建立了JCH与确定超图Turán数的长期悬而未决的问题之间的强联系。然后，我们使用这种联系来证明改进的SDP差距(相对于文献中现有的因素)、分叉-均值和k-中值目标。
k-median andk-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly inℓp-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives inℓp-metrics.We introduce a new hypothesis called theJohnson Coverage Hypothesis(JCH), which roughly asserts that the well-studied Maxk-Coverage problem on set systems is hard to approximate to a factor greater than (1–1/e), even when the membership graph of the set system is a subgraph of the Johnson graph. We then show that together with generalizations of the embedding techniques introduced by Cohen-Addad and Karthik (FOCS '19), JCH implies hardness of approximation results fork-median andk-means inℓp-metrics for factors which are close to the ones obtained for general metrics. In particular, assuming JCH we show that it is hard to approximate thek-means objective:Discrete case: To a factor of 3.94 in theℓ1-metric and to a factor of 1.73 in theℓ2-metric; this improves upon the previous factor of 1.56 and 1.17 respectively, obtained under the Unique Games Conjecture (UGC).Continuous case: To a factor of 2.10 in theℓ1-metric and to a factor of 1.36 in theℓ2-metric; this improves upon the previous factor of 1.07 in theℓ2-metric obtained under UGC (and to the best of our knowledge, the continuous case ofk-means inℓ1-metric was not previously analyzed in literature).We also obtain similar improvements under JCH for thek-median objective.Additionally, we prove a weak version of JCH using the work of Dinur et al. (SICOMP ‘05) on Hypergraph Vertex Cover, and recover all the results stated above of Cohen-Addad and Karthik (FOCS ‘19) to (nearly) the same inapproximability factors but now under the standard NP ≠ P assumption (instead of UGC).Finally, we establish a strong connection between JCH and the long standing open problem of determining the Hypergraph Turán number. We then use this connection to prove improved SDP gaps (over the existing factors in literature) fork-means andk-median objectives.