License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.2
URN: urn:nbn:de:0030-drops-63435
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6343/
Go to the corresponding LIPIcs Volume Portal

Svensson, Ola

Algorithms with Provable Guarantees for Clustering (Invited Talk)

pdf-format:
LIPIcs-ESA-2016-2.pdf (0.2 MB)

Abstract

In this talk, we give an overview of the current best approximation algorithms for fundamental clustering problems, such as k-center, k-median, k-means, and facility location. We focus on recent progress and point out several important open problems.


For the uncapacitated versions, a variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to a standard linear programming relaxation. This has given a uniform way of addressing these problems resulting in small constant approximation guarantees.

In spite of this impressive progress, it remains a challenging open problem to give tight guarantees. Moreover, this collection of powerful algorithmic techniques is not easily applicable to the capacitated setting. In fact, there is no simple strong convex relaxation known for the capacitated versions. As a result, our understanding of these problems is significantly weaker and several fundamental questions remain open.

BibTeX - Entry

@InProceedings{svensson:LIPIcs:2016:6343,
  author =	{Ola Svensson},
  title =	{{Algorithms with Provable Guarantees for Clustering (Invited Talk)}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6343},
  URN =		{urn:nbn:de:0030-drops-63435},
  doi =		{10.4230/LIPIcs.ESA.2016.2},
  annote =	{Keywords: Approximation algorithms, clustering}
}

Keywords: Approximation algorithms, clustering
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI