Abstract
We present a novel local improvement scheme for graph partitions that allows to enforce strict balance constraints. Using negative cycle detection algorithms this scheme combines local searches that individually violate the balance constraint into a more global feasible improvement. We combine this technique with an algorithm to balance unbalanced solutions and integrate it into a parallel multi-level evolutionary algorithm, KaFFPaE, to tackle the problem. Overall, we obtain a system that is fast on the one hand and on the other hand is able to improve or reproduce many of the best known perfectly balanced partitioning results reported in the Walshaw benchmark.
This paper is a short version of the TR [14].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bader, D., Meyerhenke, H., Sanders, P., Wagner, D.: 10th DIMACS Implementation Challenge - Graph Partitioning and Graph Clustering
Benlic, U., Hao, J.-K.: An effective multilevel tabu search approach for balanced graph partitioning. Computers & OR 38(7), 1066–1075 (2011)
Bichot, C., Siarry, P. (eds.): Graph Partitioning. Wiley (2011)
Cherkassky, B.V., Goldberg, A.V.: Negative-cycle detection algorithms. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 349–363. Springer, Heidelberg (1996)
Delling, D., Werneck, R.F.: Better bounds for graph bisection. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 407–418. Springer, Heidelberg (2012)
Fiduccia, C.M., Mattheyses, R.M.: A Linear-Time Heuristic for Improving Network Partitions. In: 19th Conference on Design Automation, pp. 175–181 (1982)
Galinier, P., Boujbel, Z., Coutinho Fernandes, M.: An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 1–22 (2011)
Holtgrewe, M., Sanders, P., Schulz, C.: Engineering a Scalable High Quality Graph Partitioner. In: 24th IEEE IPDPS, pp. 1–12 (2010)
Karypis, G., Kumar, V.: Parallel multilevel k-way partitioning scheme for irregular graphs. SIAM Review 41(2), 278–300 (1999)
Osipov, V., Sanders, P.: n-level graph partitioning. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 278–289. Springer, Heidelberg (2010)
Pellegrini, F.: http://www.labri.fr/perso/pelegrin/scotch/
Sanders, P., Schulz, C.: Engineering multilevel graph partitioning algorithms. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 469–480. Springer, Heidelberg (2011)
Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: ALENEX, pp. 16–29. SIAM/Omnipress (2012)
Sanders, P., Schulz, C.: Think Locally, Act Globally: Perfectly Balanced Graph Partitioning. Technical Report. arXiv:1210.0477 (2012)
Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph-partitioning. J. of Global Optimization 29(2), 225–241 (2004)
Walshaw, C., Cross, M.: Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm. SIAM Journal on Scientific Computing 22(1), 63–80 (2000)
Walshaw, C., Cross, M.: JOSTLE: Parallel Multilevel Graph-Partitioning Software – An Overview. In: Mesh Partitioning Techniques and Domain Decomposition Techniques, pp. 27–58. Civil-Comp Ltd. (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sanders, P., Schulz, C. (2013). Think Locally, Act Globally: Highly Balanced Graph Partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds) Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38527-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-38527-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38526-1
Online ISBN: 978-3-642-38527-8
eBook Packages: Computer ScienceComputer Science (R0)