License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.4
URN: urn:nbn:de:0030-drops-89399
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8939/
Go to the corresponding LIPIcs Volume Portal

Henzinger, Alexandra ; Noe, Alexander ; Schulz, Christian

ILP-based Local Search for Graph Partitioning

pdf-format:
LIPIcs-SEA-2018-4.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{henzinger_et_al:LIPIcs:2018:8939,
  author =	{Alexandra Henzinger and Alexander Noe and Christian Schulz},
  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 =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8939},
  URN =		{urn:nbn:de:0030-drops-89399},
  doi =		{10.4230/LIPIcs.SEA.2018.4},
  annote =	{Keywords: Graph Partitioning, Integer Linear Programming}
}

Keywords: Graph Partitioning, Integer Linear Programming
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI