Approximation algorithms for aversion \(k\)-clustering via local \(k\)-median. (English) Zbl 1388.68308
Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 66, 13 p. (2016).
Summary: 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.
For the entire collection see [Zbl 1351.68012].
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.
For the entire collection see [Zbl 1351.68012].
MSC:
| 68W25 | Approximation algorithms |
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
