Name
Abstract | ||
|---|---|---|
We resolve in the affirmative a question of R.B. Boppana and T. Bui: whether simulated annealing can with high probability and in polynomial time, find the optimal bisection of a random graph an Gnpr when p-r=(ΘnΔ-2) for Δ⩽2. (The random graph model Gnpr 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 3/2<⩽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 |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/SFCS.1993.366878 | Palo Alto, CA |
Keywords | Field | DocType |
random graph,spl theta,simulated annealing,high probability,spl delta,sub npr,higher density p,unique smallest bisection,spl epsi,graph bisection,optimal bisection,computer science,polynomial time,metropolis algorithm,computational modeling,polynomials,computational geometry,stochastic processes,energy states,temperature control | Simulated annealing,Discrete mathematics,Combinatorics,Random graph,Metropolis–Hastings algorithm,Bisection,Graph bisection,Computational geometry,Adaptive simulated annealing,Time complexity,Mathematics | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-8186-4370-6 | 41 |
PageRank | References | Authors |
8.46 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| JerrumMark | 1 | 199 | 33.55 |
| Gregory B. Sorkin | 2 | 597 | 89.64 |