{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:12Z","timestamp":1750220652634,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Gordon Fund for System Engineering"},{"DOI":"10.13039\/501100016296","name":"Israel National Cyber Directorate","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016296","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100018707","name":"Technion Hiroshi Fujiwara Cyber Security Research Center","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100018707","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1595\/19 and 1367\/2016"],"award-info":[{"award-number":["1595\/19 and 1367\/2016"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"German-Israeli Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Taub Family Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>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 that 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.<\/jats:p>","DOI":"10.1145\/3386121","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Clustering in Hypergraphs to Minimize Average Edge Service Time"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4064-1238","authenticated-orcid":false,"given":"Ori","family":"Rottenstreich","sequence":"first","affiliation":[{"name":"Technion"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Bar-Ilan University and Google"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"IEEE. 2014. IEEE Xplore\u2014INFOCOM 2014. Retrieved May 1 2020 from https:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=6839150. IEEE. 2014. IEEE Xplore\u2014INFOCOM 2014. Retrieved May 1 2020 from https:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=6839150."},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","author":"CAIDA.","year":"2015","unstructured":"CAIDA. 2015 . CAIDA Anonymized 2015 Internet Trace Equinix\u2014Chicago . Retrieved May 18, 2020 from https:\/\/www.caida.org\/data\/passive\/passive_2015_dataset.xml. CAIDA. 2015. CAIDA Anonymized 2015 Internet Trace Equinix\u2014Chicago. Retrieved May 18, 2020 from https:\/\/www.caida.org\/data\/passive\/passive_2015_dataset.xml."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2007.05.024"},{"volume-title":"Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905)","author":"Agarwal Sameer","key":"e_1_2_1_4_1","unstructured":"Sameer Agarwal , Jongwoo Lim , Lihi Zelnik-Manor , Pietro Perona , David J. Kriegman , and Serge J. Belongie . 2005. Beyond pairwise clustering . In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905) . Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David J. Kriegman, and Serge J. Belongie. 2005. Beyond pairwise clustering. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124330"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"volume-title":"A survey of correlation clustering. COMS E6998: Advanced Topics in Computational Learning Theory","author":"Becker Hila","key":"e_1_2_1_8_1","unstructured":"Hila Becker . 2005. A survey of correlation clustering. COMS E6998: Advanced Topics in Computational Learning Theory . Columbia University , 1\u201310. Hila Becker. 2005. A survey of correlation clustering. COMS E6998: Advanced Topics in Computational Learning Theory. Columbia University, 1\u201310."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/040616541"},{"key":"e_1_2_1_10_1","volume-title":"Szyld","author":"Bru Rafael","year":"2005","unstructured":"Rafael Bru , Francisco Pedroche , and Daniel B . Szyld . 2005 . C\u00e1lculo del vector PageRank de Google mediante el m\u00e9todo aditivo de Schwarz. In Congreso de M\u00e9todos Num\u00e9ricos en Ingenier\u00eda . Rafael Bru, Francisco Pedroche, and Daniel B. Szyld. 2005. C\u00e1lculo del vector PageRank de Google mediante el m\u00e9todo aditivo de Schwarz. In Congreso de M\u00e9todos Num\u00e9ricos en Ingenier\u00eda."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.226"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218511"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/13.2.156"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1979.4766909"},{"key":"e_1_2_1_16_1","unstructured":"Ran Duan. 2014. A simpler scaling algorithm for weighted matching in general graphs. arXiv:1411.1919. Ran Duan. 2014. A simpler scaling algorithm for weighted matching in general graphs. arXiv:1411.1919."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/01969727408546059"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/568574.568575"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050449"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_2_1_23_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman , New York, NY. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, NY."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804034"},{"key":"e_1_2_1_25_1","series-title":"The IBM Research Symposia Series","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . The IBM Research Symposia Series . IBM Thomas J. Watson Research Center , 85\u2013103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. The IBM Research Symposia Series. IBM Thomas J. Watson Research Center, 85\u2013103."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS\u201912)","author":"Leordeanu Marius","year":"2012","unstructured":"Marius Leordeanu and Cristian Sminchisescu . 2012 . Efficient hypergraph clustering . In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS\u201912) . Marius Leordeanu and Cristian Sminchisescu. 2012. Efficient hypergraph clustering. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS\u201912)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_2_1_28_1","volume-title":"Tarjan","author":"Mishra Nina","year":"2007","unstructured":"Nina Mishra , Robert Schreiber , Isabelle Stanton , and Robert E . Tarjan . 2007 . Clustering social networks. In Algorithms and Models for the Web-Graph. Springer , 56--67. Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan. 2007. Clustering social networks. In Algorithms and Models for the Web-Graph. Springer, 56--67."},{"key":"e_1_2_1_29_1","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","volume":"14","author":"Ng Andrew Y.","year":"2002","unstructured":"Andrew Y. Ng , Michael I. Jordan , and Yair Weiss . 2002 . On spectral clustering: Analysis and an algorithm . Advances in Neural Information Processing Systems 14 (2002), 849 -- 856 . Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. 2002. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems 14 (2002), 849--856.","journal-title":"Advances in Neural Information Processing Systems"},{"volume-title":"Computational Complexity","author":"Papadimitriou C. H.","key":"e_1_2_1_30_1","unstructured":"C. H. Papadimitriou . 1994. Computational Complexity . Addison-Wesley , Reading, MA . C. H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00018-011-0846-8"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2556670"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11744085_46"},{"volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201906)","author":"Daniel","key":"e_1_2_1_34_1","unstructured":"Daniel A. Spielmat and Shang-Hua Teng. 1996. Spectral partitioning works: Planar graphs and finite element meshes . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201906) . Daniel A. Spielmat and Shang-Hua Teng. 1996. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201906)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Dengyong Zhou Jiayuan Huang and Bernhard Sch\u00f6lkopf. 2006. Learning with hypergraphs: Clustering classification and embedding. In Advances in Neural Information Processing Systems 19 (NIPS\u201906). Dengyong Zhou Jiayuan Huang and Bernhard Sch\u00f6lkopf. 2006. Learning with hypergraphs: Clustering classification and embedding. In Advances in Neural Information Processing Systems 19 (NIPS\u201906).","DOI":"10.7551\/mitpress\/7503.003.0205"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:24Z","timestamp":1750197744000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3386121"],"URL":"https:\/\/doi.org\/10.1145\/3386121","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}