文章基本信息

标题：Clustering in Hypergraphs to Minimize Average Edge Service Time
本地全文：下载
作者：Ori Rottenstreich ; Haim Kaplan ; Avinatan Hassidim 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：64:1-64:14
DOI：10.4230/LIPIcs.ESA.2017.64
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Clustering; average cover time; hypergraphs; set cover