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.FSTTCS.2013.401
URN: urn:nbn:de:0030-drops-43898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4389/
Go to the corresponding LIPIcs Volume Portal

Chalermsook, Parinya ; Venkatasubramanian, Suresh

Clustering With Center Constraints

pdf-format:
30.pdf (0.5 MB)

Abstract

In the classical maximum independent set problem, we are given a graph G of "conflicts" and are asked to find a maximum conflict-free subset. If we think of the remaining nodes as being "assigned" (at unit cost each) to one of these independent vertices and ask for an assignment of minimum cost, this yields the vertex cover problem.
In this paper, we consider a more general scenario where the assignment costs might be given by a distance metric d (which can be unrelated to G) on the underlying set of vertices.

This problem, in addition to being a natural generalization of vertex cover and an interesting variant of the k-median problem, also has connection to constrained clustering and database repair.

Understanding the relation between the conflict structure (the graph) and the distance structure (the metric) for this problem turns out to be the key to isolating its complexity. We show that when the two structures are unrelated, the problem inherits a trivial upper bound from vertex cover and provide an almost matching lower bound on hardness of approximation. We then prove a number of lower and upper bounds that depend on the relationship between the two structures, including polynomial time algorithms for special graphs.

BibTeX - Entry

@InProceedings{chalermsook_et_al:LIPIcs:2013:4389,
  author =	{Parinya Chalermsook and Suresh Venkatasubramanian},
  title =	{{Clustering With Center Constraints}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{401--412},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4389},
  URN =		{urn:nbn:de:0030-drops-43898},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.401},
  annote =	{Keywords: Clustering, vertex cover, approximation algorithms}
}

Keywords: Clustering, vertex cover, approximation algorithms
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

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