DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.4

ILP-based Local Search for Graph Partitioning

Authors: Alexandra Henzinger, Alexander Noe, and Christian Schulz

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract

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.

Cite as

Alexandra Henzinger, Alexander Noe, and Christian Schulz. ILP-based Local Search for Graph Partitioning. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.SEA.2018.4,
  author =	{Henzinger, Alexandra and Noe, Alexander and Schulz, Christian},
  title =	{{ILP-based Local Search for Graph Partitioning}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.4},
  URN =		{urn:nbn:de:0030-drops-89399},
  doi =		{10.4230/LIPIcs.SEA.2018.4},
  annote =	{Keywords: Graph Partitioning, Integer Linear Programming}
}

Search Results

Documents authored by Henzinger, Alexandra

ILP-based Local Search for Graph Partitioning

Abstract

Cite as

Thanks for your feedback!

Could not send message