{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:50:45Z","timestamp":1762876245192,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,7,4]],"date-time":"2020-07-04T00:00:00Z","timestamp":1593820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SCHU 2567\/1-2"],"award-info":[{"award-number":["SCHU 2567\/1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>Computing high-quality graph partitions is a challenging problem with numerous applications. In this article, we present a novel meta-heuristic for the balanced graph partitioning problem. Our approach is based on integer linear programs that solve the partitioning problem to optimality. However, since those programs typically do not scale to large inputs, we adapt them to heuristically improve a given partition. We do so by defining a much smaller model that allows us to use symmetry breaking and other techniques that make the approach scalable. For example, in Walshaw\u2019s well-known benchmark tables, we are able to improve roughly half of all entries when the number of blocks is high. Additionally, we include our techniques into a memetic framework and develop a crossover operation based on the proposed techniques.<\/jats:p>","DOI":"10.1145\/3398634","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T18:07:25Z","timestamp":1599761245000},"page":"1-26","source":"Crossref","is-referenced-by-count":15,"title":["ILP-Based Local Search for Graph Partitioning"],"prefix":"10.1145","volume":"25","author":[{"given":"Alexandra","family":"Henzinger","sequence":"first","affiliation":[{"name":"Stanford University, Serra Mall, Stanford, CA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4711-3323","authenticated-orcid":false,"given":"Alexander","family":"Noe","sequence":"additional","affiliation":[{"name":"University of Vienna, Faculty of Computer Science, W\u00e4hringer Stra\u00dfe 29, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-3506","authenticated-orcid":false,"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Vienna, Faculty of Computer Science, W\u00e4hringer Stra\u00dfe 29, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2020,7,4]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/0167-9260(95)00008-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/S0166-218X(98)00083-3"},{"volume":"5035","volume-title":"Proc. of the 13th International Conference on Integer Programming and Combinatorial Optimization (LNCS)","author":"Armbruster M.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"crossref","unstructured":"D. A. Bader H. Meyerhenke P. Sanders C. Schulz A. Kappes and D. Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining. Springer 73--82.  D. A. Bader H. Meyerhenke P. Sanders C. Schulz A. Kappes and D. Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining. Springer 73--82.","key":"e_1_2_1_5_1","DOI":"10.1007\/978-1-4614-6170-8_23"},{"unstructured":"C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley.  C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley.","key":"e_1_2_1_6_1"},{"volume-title":"Proc. of the 52nd European Study Group Mathematics with Industry Amsterdam 2005","year":"2006","author":"Bisseling Rob H.","key":"e_1_2_1_7_1"},{"volume-title":"A Multi-Level Framework for Bisection Heuristics. Student thesis","author":"Brillout R.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/0020-0190(92)90140-Q"},{"doi-asserted-by":"crossref","unstructured":"A. Bulu\u00e7 H. Meyerhenke I. Safro P. Sanders and C. Schulz. 2016. Recent advances in graph partitioning. In Algorithm\u00a0Engineering. Springer 117--158.  A. Bulu\u00e7 H. Meyerhenke I. Safro P. Sanders and C. Schulz. 2016. Recent advances in graph partitioning. In Algorithm\u00a0Engineering. Springer 117--158.","key":"e_1_2_1_10_1","DOI":"10.1007\/978-3-319-49487-6_4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/2049662.2049670"},{"volume":"6630","volume-title":"Proc. of the 10th International Symposium on Experimental Algorithms (LCNS)","author":"Delling D.","key":"e_1_2_1_12_1"},{"volume-title":"Proc. of the 12th Workshop on Algorithm\u00a0Engineering and Experimentation (ALENEX\u201912)","author":"Delling D.","key":"e_1_2_1_13_1"},{"volume":"7501","volume-title":"Proc. of the 20th European Symposium on Algorithms (LNCS)","author":"Delling D.","key":"e_1_2_1_14_1"},{"volume":"6942","volume-title":"Proc. of the 19th European Conference on Algorithms (LNCS)","author":"Feldmann A.","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/s10472-005-9001-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.5555\/3113618.3114091"},{"volume-title":"Proc. of the 19th Conference on Design Automation. 175--181","author":"Fiduccia C. M.","key":"e_1_2_1_18_1"},{"volume":"7484","volume-title":"Proc. of Euro-Par 2012 Parallel Processing (LNCS)","author":"Fietz J.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/s10479-011-0983-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1137\/0710032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1007\/s10107-011-0503-x"},{"unstructured":"M. Hein and S. Setzer. 2011. Beyond spectral clustering\u2014Tight relaxations of balanced graph cuts. In Advances in Neural Information Processing Systems. 2366--2374.  M. Hein and S. Setzer. 2011. Beyond spectral clustering\u2014Tight relaxations of balanced graph cuts. In Advances in Neural Information Processing Systems. 2366--2374.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","volume-title":"17th International Symposium on Experimental Algorithms, SEA 2018","volume":"103","author":"Henzinger Alexandra","year":"2018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1287\/ijoc.12.3.177.12637"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/S1064827595287997"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"volume":"6049","volume-title":"Proc. of the 9th International Symposium on Experimental Algorithms (LNCS)","author":"Kieritz T.","key":"e_1_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.2307\/1910129"},{"key":"e_1_2_1_30_1","volume-title":"Geoinformation und Mobilit\u00e4t--Von Der Forschung Zur Praktischen Anwendung","volume":"22","author":"Lauther U.","year":"2004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/s10107-002-0342-x"},{"volume":"7276","volume-title":"Proc. of the 11th International Symposium on Experimental Algorithms (SEA\u201912)","author":"Luxen D.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1007\/s11590-014-0754-6"},{"key":"e_1_2_1_34_1","article-title":"Partitioning graphs to speedup Dijkstra\u2019s algorithm","volume":"11","author":"M\u00f6hring R. H.","year":"2007","journal-title":"J. Exp. Algorithmics (JEA)"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.5555\/645560.658570"},{"volume":"6942","volume-title":"Proc. of the 19th European Symposium on Algorithms (LNCS)","author":"Sanders P.","key":"e_1_2_1_36_1"},{"volume-title":"Proc. of the 12th International Symposium on Experimental Algorithms (SEA\u201913)","author":"Sanders P.","key":"e_1_2_1_37_1"},{"unstructured":"K. Schloegel G. Karypis and V. Kumar. 2003. Graph partitioning for high performance scientific simulations. In The Sourcebook of Parallel Computing. 491--541.  K. Schloegel G. Karypis and V. Kumar. 2003. Graph partitioning for high performance scientific simulations. In The Sourcebook of Parallel Computing. 491--541.","key":"e_1_2_1_38_1"},{"doi-asserted-by":"crossref","unstructured":"C. Schulz and D. Strash. 2018. Graph partitioning formulations and applications to Big Data. Encyclopedia on Big Data Technologies (2018).  C. Schulz and D. Strash. 2018. Graph partitioning formulations and applications to Big Data. Encyclopedia on Big Data Technologies (2018).","key":"e_1_2_1_39_1","DOI":"10.1007\/978-3-319-63962-8_312-2"},{"volume":"2832","volume-title":"Proc. of the 11th European Symposium on Algorithms (LNCS)","author":"Sellmann M.","key":"e_1_2_1_40_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1007\/3-540-44676-1_33"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1023\/B:JOGO.0000042115.44455.f3"},{"key":"e_1_2_1_43_1","first-page":"583","article-title":"Cluster ensembles\u2014A knowledge reuse framework for combining multiple partitions","volume":"3","author":"Strehl Alexander","year":"2002","journal-title":"J. Mach. Learn. Res."},{"unstructured":"C. Walshaw. 2000. Walshaw Partitioning Benchmark. Retrieved from http:\/\/staffweb.cms.gre.ac.uk\/wc06\/partition\/.  C. Walshaw. 2000. Walshaw Partitioning Benchmark. Retrieved from http:\/\/staffweb.cms.gre.ac.uk\/wc06\/partition\/.","key":"e_1_2_1_44_1"},{"volume-title":"JOSTLE: Parallel multilevel graph-partitioning software -- An overview. In Mesh Partitioning Techniques and Domain Decomposition Techniques. 27--58.","year":"2007","author":"Walshaw C.","key":"e_1_2_1_45_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3398634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:31Z","timestamp":1750199611000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,4]]},"references-count":44,"alternative-id":["10.1145\/3398634"],"URL":"https:\/\/doi.org\/10.1145\/3398634","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,7,4]]}}}