Cut Size Statistics of Graph Bisection Heuristics

DOI10.1137/S1052623497321523MaRDI QIDQ4943616zbMATH OpenOpenAlexWikidataFDO

Authors G. R. Schreiber, O. C. Martin

Publication date 19 March 2000

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9804027

zbMATH Keywords

graph partitioningheuristicsrankingself-averaging

Mathematics Subject Classification ID

Statistical thermodynamics (82B30) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Combinatorial optimization (90C27)

Abstract: We investigate the statistical properties of cut sizes generated by heuristic algorithms which solve approximately the graph bisection problem. On an ensemble of sparse random graphs, we find empirically that the distribution of the cut sizes found by ``local algorithms becomes peaked as the number of vertices in the graphs becomes large. Evidence is given that this distribution tends towards a Gaussian whose mean and variance scales linearly with the number of vertices of the graphs. Given the distribution of cut sizes associated with each heuristic, we provide a ranking procedure which takes into account both the quality of the solutions and the speed of the algorithms. This procedure is demonstrated for a selection of local graph bisection heuristics.

Recommendations

• A spectral heuristic for bisecting random graphs
• scientific article; zbMATH DE number 910878
• scientific article; zbMATH DE number 1418276
• A spectral heuristic for bisecting random graphs
• The peculiar phase structure of random graph bisection

Cited in

(5)

• A variable neighborhood search heuristic for nonnegative matrix factorization with application to microarray data
• Hybrid metaheuristics: an introduction
• scientific article; zbMATH DE number 828046 (Why is no real title available?)
• Bipartitioning of directed and mixed random graphs
• Statistical mechanics methods and phase transitions in optimization problems

This page was built for publication: Cut Size Statistics of Graph Bisection Heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943616)