dc.contributor.author | Ahmadian, S | |
dc.contributor.author | Norouzi-Fard, A | |
dc.contributor.author | Svensson, O | |
dc.contributor.author | Ward, J | |
dc.date.accessioned | 2020-12-03T16:15:36Z | |
dc.date.available | 2020-12-03T16:15:36Z | |
dc.date.issued | 2020-01-01 | |
dc.identifier.issn | 0097-5397 | |
dc.identifier.uri | https://qmro.qmul.ac.uk/xmlui/handle/123456789/69012 | |
dc.description.abstract | Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for $k$-means in Euclidean space with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of $9+\epsilon$, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of $k$-means and (2) satisfy the hard constraint that at most $k$ clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard linear programming (LP) relaxation. Our techniques are quite general, and we also show improved guarantees for $k$-median in Euclidean metrics and for a generalization of $k$-means in which the underlying metric is not required to be Euclidean. | en_US |
dc.format.extent | focs17-97-focs17-156 - ? | |
dc.publisher | Society for Industrial and Applied Mathematics | en_US |
dc.relation.ispartof | SIAM Journal on Computing | |
dc.title | Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms | en_US |
dc.type | Article | en_US |
dc.rights.holder | © 2019, Society for Industrial and Applied Mathematics Read More: https://epubs.siam.org/doi/10.1137/18M1171321 | |
dc.identifier.doi | 10.1137/18m1171321 | |
pubs.issue | 4 | en_US |
pubs.notes | Not known | en_US |
pubs.volume | 49 | en_US |
rioxxterms.funder | Default funder | en_US |
rioxxterms.identifier.project | Default project | en_US |