{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T06:11:49Z","timestamp":1706767909665},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,6]],"date-time":"2013-03-06T00:00:00Z","timestamp":1362528000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00453-013-9761-8","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T16:43:30Z","timestamp":1362501810000},"page":"844-863","source":"Crossref","is-referenced-by-count":4,"title":["On the Advantage of Overlapping Clusters for Minimizing Conductance"],"prefix":"10.1007","volume":"69","author":[{"given":"Rohit","family":"Khandekar","sequence":"first","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,6]]},"reference":[{"key":"9761_CR1","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1250790.1250888","volume-title":"STOC","author":"A. Agarwal","year":"2007","unstructured":"Agarwal, A., Alon, N., Charikar, M.: Improved approximation for directed cut problems. In: STOC, pp. 671\u2013680 (2007)"},{"key":"9761_CR2","first-page":"475","volume-title":"FOCS","author":"R. Andersen","year":"2006","unstructured":"Andersen, R., Chung, F.R.K., Lang, K.J.: Local graph partitioning using pagerank vectors. In: FOCS, pp. 475\u2013486 (2006)"},{"key":"9761_CR3","volume-title":"ACM Conference on Web search and Data Mining","author":"R. Andersen","year":"2012","unstructured":"Andersen, R., Gleich, D., Mirrokni, V.: Overlapping clustering for distributed computation. In: ACM Conference on Web search and Data Mining (2012)"},{"key":"9761_CR4","volume-title":"ACM EC","author":"S. Arora","year":"2012","unstructured":"Arora, S., Ge, R., Sachdeva, S., Schoenebeck, G.: Finding overlapping communities in social networks: toward a rigorous approach. In: ACM EC (2012)"},{"issue":"5","key":"9761_CR5","doi-asserted-by":"crossref","first-page":"1748","DOI":"10.1137\/080731049","volume":"39","author":"S. Arora","year":"2010","unstructured":"Arora, S., Hazan, E., Kale, S.: $O(\\sqrt{\\log(n)})$ approximation to sparsest cut in $\\tilde{o}(n^{{2}})$ time. SIAM J. Comput. 39(5), 1748\u20131771 (2010)","journal-title":"SIAM J. Comput."},{"key":"9761_CR6","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1145\/1060590.1060673","volume-title":"STOC \u201905: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing","author":"S. Arora","year":"2005","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: STOC \u201905: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 553\u2013562. ACM Press, New York (2005)"},{"key":"9761_CR7","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1145\/1007352.1007355","volume-title":"STOC","author":"S. Arora","year":"2004","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. In: STOC, pp. 222\u2013231 (2004)"},{"key":"9761_CR8","unstructured":"Balcan, M., Borgs, C., Braverman, M., Chayes, J.T., Teng, S.: I like her more than you: self-determined communities. CoRR (2012). arXiv:1201.4899"},{"key":"9761_CR9","first-page":"17","volume-title":"FOCS","author":"N. Bansal","year":"2011","unstructured":"Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min-max graph partitioning and small set expansion. In: FOCS, pp. 17\u201326 (2011)"},{"key":"9761_CR10","first-page":"19","volume-title":"ICML","author":"A. Blum","year":"2001","unstructured":"Blum, A., Chawla, S.: Learning from labeled and unlabeled data using graph mincuts. In: ICML, pp. 19\u201326 (2001)"},{"key":"9761_CR11","doi-asserted-by":"crossref","unstructured":"Brandes, U., Gaertler, M., Wagner, D.: Engineering graph clustering: models and experimental evaluation. ACM J.\u00a0Exp. Algorithmics 1(1) (2007)","DOI":"10.1145\/1227161.1227162"},{"issue":"3","key":"9761_CR12","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. J.\u00a0Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9761_CR13","first-page":"102","volume-title":"SODA \u201905: Proceedings of the Sixteenth annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Chawla","year":"2005","unstructured":"Chawla, S., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In: SODA \u201905: Proceedings of the Sixteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp. 102\u2013111. SIAM, Philadelphia (2005)"},{"issue":"3","key":"9761_CR14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s00493-005-0015-5","volume":"25","author":"J. Cheriyan","year":"2005","unstructured":"Cheriyan, J., Karloff, H., Rabani, Y.: Approximating directed multicuts. Combinatorica 25(3), 251\u2013269 (2005)","journal-title":"Combinatorica"},{"key":"9761_CR15","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/1132516.1132593","volume-title":"STOC \u201906: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing","author":"J. Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Khanna, S.: Hardness of cut problems in directed graphs. In: STOC \u201906: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 527\u2013536. ACM Press, New York (2006)"},{"key":"9761_CR16","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Khanna, S.: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2) (2009)","DOI":"10.1145\/1502793.1502795"},{"key":"9761_CR17","first-page":"33","volume-title":"Symposium on Theory of Computing","author":"I. Dinur","year":"2002","unstructured":"Dinur, I., Safra, S.: The importance of being biased. In: Symposium on Theory of Computing, pp. 33\u201342 (2002)"},{"issue":"6","key":"9761_CR18","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"28","author":"G. Even","year":"1999","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM J. Comput. 28(6), 2187\u20132214 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9761_CR19","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"9761_CR20","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9761_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"9761_CR22","volume-title":"ICWSM","author":"U. Gargi","year":"2011","unstructured":"Gargi, U., Lu, W., Mirrokni, V., Yoon, S.: Large-scale community detection on youtube. In: ICWSM (2011)"},{"key":"9761_CR23","first-page":"454","volume-title":"Symposium on Discrete Algorithms","author":"A. Gupta","year":"2003","unstructured":"Gupta, A.: Improved results for directed multicut. In: Symposium on Discrete Algorithms, pp. 454\u2013455 (2003)"},{"key":"9761_CR24","first-page":"34","volume-title":"SPAA","author":"C. Harrelson","year":"2003","unstructured":"Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: SPAA, pp. 34\u201343 (2003)"},{"key":"9761_CR25","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/1132516.1132574","volume-title":"STOC","author":"R. Khandekar","year":"2006","unstructured":"Khandekar, R., Rao, S., Vazirani, U.V.: Graph partitioning using single commodity flows. In: STOC, pp. 385\u2013390 (2006)"},{"issue":"4","key":"9761_CR26","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1002\/net.20066","volume":"45","author":"Y. Kortsarts","year":"2005","unstructured":"Kortsarts, Y., Kortsarz, G., Nutov, Z.: Greedy approximation algorithms for directed multicuts. Networks 45(4), 214\u2013217 (2005)","journal-title":"Networks"},{"key":"9761_CR27","first-page":"92","volume-title":"SODA \u201905: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J.R. Lee","year":"2005","unstructured":"Lee, J.R.: On distance scales, embeddings, and efficient relaxations of the cut cone. In: SODA \u201905: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 92\u2013101. SIAM, Philadelphia (2005)"},{"key":"9761_CR28","first-page":"154","volume-title":"STACS","author":"R. Lep\u00e8re","year":"2002","unstructured":"Lep\u00e8re, R., Rapine, C.: An asymptotic o(ln rho\/ln ln rho)-approximation algorithm for the scheduling problem with duplication on large communication delay graphs. In: STACS, pp. 154\u2013165 (2002)"},{"key":"9761_CR29","first-page":"56","volume-title":"WAW","author":"N. Mishra","year":"2007","unstructured":"Mishra, N., Schreiber, R., Stanton, I., Tarjan, R.E.: Clustering social networks. In: WAW, pp. 56\u201367 (2007)"},{"key":"9761_CR30","first-page":"43","volume-title":"FOCS","author":"H. R\u00e4cke","year":"2002","unstructured":"R\u00e4cke, H.: Minimizing congestion in general networks. In: FOCS, pp. 43\u201352 (2002)"},{"key":"9761_CR31","first-page":"255","volume-title":"STOC","author":"H. R\u00e4cke","year":"2008","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC, pp. 255\u2013264 (2008)"},{"key":"9761_CR32","first-page":"255","volume-title":"STOC","author":"H. R\u00e4cke","year":"2008","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC, pp. 255\u2013264 (2008)"},{"issue":"1","key":"9761_CR33","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.automatica.2011.09.019","volume":"48","author":"T. Sahai","year":"2012","unstructured":"Sahai, T., Speranzon, A., Banaszuk, A.: Hearing the clusters of a graph: a distributed algorithm. Automatica 48(1), 15\u201324 (2012)","journal-title":"Automatica"},{"issue":"1","key":"9761_CR34","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H. Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"9761_CR35","unstructured":"Shmoys, D.: Cut problems and their applications to divide-andconquer (1996)"},{"key":"9761_CR36","volume-title":"ICML","author":"A.P. Streich","year":"2009","unstructured":"Streich, A.P., Frank, M., Basin, D., Buhmann, J.M.: Multi-assignment clustering for boolean data. In: ICML (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9761-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9761-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9761-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T23:06:42Z","timestamp":1688080002000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9761-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,6]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9761"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9761-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,6]]}}}