1 Search Results for "Rottenstreich, Ori"

Document
DOI: 10.4230/LIPIcs.ESA.2017.64
Clustering in Hypergraphs to Minimize Average Edge Service Time

Authors: Ori Rottenstreich, Haim Kaplan, and Avinatan Hassidim

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

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.
Cite as

Ori Rottenstreich, Haim Kaplan, and Avinatan Hassidim. Clustering in Hypergraphs to Minimize Average Edge Service Time. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{rottenstreich_et_al:LIPIcs.ESA.2017.64,
  author =	{Rottenstreich, Ori and Kaplan, Haim and Hassidim, Avinatan},
  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 =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.64},
  URN =		{urn:nbn:de:0030-drops-78777},
  doi =		{10.4230/LIPIcs.ESA.2017.64},
  annote =	{Keywords: Clustering, average cover time, hypergraphs, set cover}
}
  • Refine by Author
  • 1 Hassidim, Avinatan
  • 1 Kaplan, Haim
  • 1 Rottenstreich, Ori

  • Refine by Classification

  • Refine by Keyword
  • 1 Clustering
  • 1 average cover time
  • 1 hypergraphs
  • 1 set cover

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact