Inapproximability of Clustering in Lp Metrics
Inapproximability of Clustering in Lp Metrics
复制标题
DOI：
10.1109/focs.2019.00040
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Vincent Cohen-Addad;K. C. S.
中科院分区：
文献类型：
--
作者：
Vincent Cohen-Addad;K. C. S.
证明最小和目标近似的困难性是一个臭名昭著的挑战。对于经典的问题，如旅行商问题，斯坦纳树问题，或k-means和k-median问题，最著名的不可逼近性界的L-p度量的维度O（log n）保持远低于1.01。在本文中，我们采取了一个重要的步骤，以提高各种L-p度量的k-均值问题的近似的硬度，更具体地说，曼哈顿（L-1），欧几里得（L-2），汉明（L-0）和Chebyshev（L-无穷大）度量的日志n和以上。我们表明，很难在O（log n）维空间中逼近k均值目标：（1）当必须从离散位置集中选择中心时，L无穷度量中的因子为3.94（即，离散情况）。这改进了Guruswami和Indyk（SODA'03）的结果，他们证明了近似的硬度小于1.01。(2)在L-1度量中为1.56的因子，在L-2度量中为1.17的因子，两者都是在离散情况下。这改进了Trevisan（SICOMP'00）的结果，Trevisan在两个度量中证明了因子小于1.01的近似硬度。(3)当中心可以放置在任意位置时，L-2度量中的因子为1.07（即，连续的情况）。这改进了李-施密特-赖特（IPL'17）的结果，他证明了近似的硬度为1.0013。我们还获得了类似的改进，在国家的最先进的硬度近似结果的k-中位数目标在各种L-p度量。我们在上面（1）中给出的硬度结果是在标准NP不等于P假设下，而上面给出的所有其余结果都是在唯一博弈猜想（UGC）下。我们可以消除对UGC的依赖，并证明上述问题的标准NP-困难，但近似因子较小。最后，我们注意到，为了获得我们的结果为L-1和L-无穷度量在O（log n）维空间，我们引入了嵌入技术相结合的转录某些通信协议的几何实现某些图形。
Proving hardness of approximation for min-sum objectives is an infamous challenge. For classic problems such as the Traveling Salesman problem, the Steiner tree problem, or the k-means and k-median problems, the best known inapproximability bounds for L-p metrics of dimension O(log n) remain well below 1.01. In this paper, we take a significant step to improve the hardness of approximation of the k-means problem in various L-p metrics, and more particularly on Manhattan (L-1), Euclidean (L-2), Hamming (L-0) and Chebyshev (L-infinity) metrics of dimension log n and above. We show that it is hard to approximate the k-means objective in O(log n) dimensional space: (1) To a factor of 3.94 in the L-infinity metric when centers have to be chosen from a discrete set of locations (i.e., the discrete case). This improves upon the result of Guruswami and Indyk (SODA'03) who proved hardness of approximation for a factor less than 1.01. (2) To a factor of 1.56 in the L-1 metric and to a factor of 1.17 in the L-2 metric, both in the discrete case. This improves upon the result of Trevisan (SICOMP'00) who proved hardness of approximation for a factor less than 1.01 in both the metrics. (3) To a factor of 1.07 in the L-2 metric, when centers can be placed at arbitrary locations, (i.e., the continuous case). This improves on a result of Lee-Schmidt-Wright (IPL'17) who proved hardness of approximation for a factor of 1.0013. We also obtain similar improvements over the state of the art hardness of approximation results for the k-median objective in various L-p metrics. Our hardness result given in (1) above, is under the standard NP is not equal to P assumption, whereas all the remaining results given above are under the Unique Games Conjecture (UGC). We can remove our reliance on UGC and prove standard NP-hardness for the above problems but for smaller approximation factors. Finally, we note that in order to obtain our result for the L-1 and L-infinity metrics in O(log n) dimensional space we introduce an embedding technique which combines the transcripts of certain communication protocols with the geometric realization of certain graphs.