TY - GEN

T1 - Approximation algorithms for aversion k-clustering via local k-median

AU - Gupta, Anupam

AU - Guruganesh, Guru

AU - Schmidt, Melanie

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Clustering

KW - K-median

KW - Primal-dual

UR - http://www.scopus.com/inward/record.url?scp=85012888038&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012888038&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2016.66

DO - 10.4230/LIPIcs.ICALP.2016.66

M3 - Conference contribution

AN - SCOPUS:85012888038

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

A2 - Rabani, Yuval

A2 - Chatzigiannakis, Ioannis

A2 - Sangiorgi, Davide

A2 - Mitzenmacher, Michael

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

Y2 - 12 July 2016 through 15 July 2016

ER -