2026-08-15T12:24:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8939 2024-03-12T11:57:58Z ddc:004 open_access

ILP-based Local Search for Graph Partitioning Henzinger, Alexandra Noe, Alexander Schulz, Christian Graph Partitioning Integer Linear Programming Computing high-quality graph partitions is a challenging problem with numerous applications. In this paper, 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's well-known benchmark tables we are able to improve roughly half of all entries when the number of blocks is high. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandra Henzinger and Alexander Noe and Christian Schulz 2018 Is Part Of LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2018.4 urn:nbn:de:0030-drops-89399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode