About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
The Metropolis algorithm for graph bisection
Abstract
We resolve in the affirmative a question of Boppana and Bui: whether simulated annealing can, with high probability and in polynomial time. find the optimal bisection of a random graph in script G signnpr when p - r = Θ(nΔ-2) for Δ ≤ 2. (The random graph model script G signnpr specifies a "planted" bisection of density r, separating two n/2-vertex subsets of slightly higher density p) We show that simulated "annealing" at an appropriate fixed temperature (i.e., the Metropolis algorithm) finds the unique smallest bisection in O(n2+ε) steps with very high probability, provided Δ > 11/6. (By using a slightly modified neighborhood structure, the number of steps can be reduced to O(n1+ε).) We leave open the question of whether annealing is effective for Δ in the range 2/3 < Δ ≤ 11/6, whose lower limit represents the threshold at which the planted bisection becomes lost amongst other random small bisections. It also remains open whether hillclimbing (i.e., annealing at temperature 0) solves the same problem; towards the latter result, Juels has recently extended our analysis and shown that random hillclimbing finds the minimum bisection with constant probability, when p - r = Ω (1) (corresponding to Δ = 2). © 1998 Elsevier Science B.V. All rights reserved.