文章基本信息

标题：Approximation Algorithms for Aversion k-Clustering via Local k-Median
本地全文：下载
作者：Anupam Gupta ; Guru Guruganesh ; Melanie Schmidt 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：66:1-66:13
DOI：10.4230/LIPIcs.ICALP.2016.66
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-point-costs. This problem is motivated by questions in generating automatic abstractions of extensive-form games. We reduce this problem to a "local" k-median problem where each facility has a prescribed radius and can only connect to clients within that radius. Our main results is a constant-factor approximation algorithm for the aversion k-clustering problem via the local k-median problem. We use a primal-dual approach; our technical contribution is a non-local rounding step which we feel is of broader interest.
关键词：Approximation algorithms; clustering; k-median; primal-dual