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.2017.64
URN: urn:nbn:de:0030-drops-78777
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7877/
Go to the corresponding LIPIcs Volume Portal

Rottenstreich, Ori ; Kaplan, Haim ; Hassidim, Avinatan

Clustering in Hypergraphs to Minimize Average Edge Service Time

pdf-format:
LIPIcs-ESA-2017-64.pdf (0.6 MB)

Abstract

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria which we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

BibTeX - Entry

@InProceedings{rottenstreich_et_al:LIPIcs:2017:7877,
  author =	{Ori Rottenstreich and Haim Kaplan and Avinatan Hassidim},
  title =	{{Clustering in Hypergraphs to Minimize Average Edge Service Time}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7877},
  URN =		{urn:nbn:de:0030-drops-78777},
  doi =		{10.4230/LIPIcs.ESA.2017.64},
  annote =	{Keywords: Clustering, average cover time, hypergraphs, set cover}
}

Keywords: Clustering, average cover time, hypergraphs, set cover
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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