Name
Abstract | ||
|---|---|---|
AbstractComputing 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’s 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3398634 | ACM Journal of Experimental Algorithmics |
DocType | Volume | Issue |
Conference | 25 | 1 |
ISSN | Citations | PageRank |
1084-6654 | 0 | 0.34 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandra Henzinger | 1 | 0 | 0.34 |
| Alexander Noe | 2 | 17 | 3.35 |
| Christian Schulz | 3 | 240 | 24.10 |