The Metropolis algorithm for graph bisection

DOI10.1016/S0166-218X(97)00133-9MaRDI QIDQ1383365zbMATH OpenOpenAlexFDO

Authors Gregory B. Sorkin, Mark Jerrum

Publication date 13 March 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(97)00133-9

zbMATH Keywords

simulated annealingMetropolis algorithmoptimal bisection of a random graph

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Markov and semi-Markov decision processes (90C40)

Recommendations

• A spectral heuristic for bisecting random graphs
• Hill-climbing finds random planted bisections
• A spectral heuristic for bisecting random graphs
• Automata, Languages and Programming
• Publication:4941836

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4128851 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Approximating the Permanent
• Average-case analysis of algorithms for matchings and related problems
• Biased random walks
• Convergence and finite-time behavior of simulated annealing
• Cooling Schedules for Optimal Annealing
• Efficient simulated annealing on fractal energy landscapes
• Large Cliques Elude the Metropolis Process
• Markov Chains with Rare Transitions and Simulated Annealing
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Optimization by simulated annealing
• Some simplified NP-complete graph problems
• Survival time of a random graph
• The effect of the density of states on the Metropolis algorithm
• The solution of some random NP-hard problems in polynomial expected time
• The time complexity of maximum matching by simulated annealing

Cited in

(23)

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Asymptotic mutual information for the balanced binary stochastic block model
• Are stable instances easy?
• scientific article; zbMATH DE number 1833396 (Why is no real title available?)
• A deterministic annealing algorithm for approximating a solution of the min-bisection problem
• Step-by-step community detection in volume-regular graphs
• Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Runtime analysis of a simple ant colony optimization algorithm
• Graph partitioning via adaptive spectral techniques
• Finding most likely solutions
• Choosing the right algorithm with hints from complexity theory
• Graph bipartitioning and statistical mechanics
• Distributed community detection in dynamic graphs
• Find Your Place: Simple Distributed Algorithms for Community Detection
• A landscape-based analysis of fixed temperature and simulated annealing
• Reconstruction and estimation in the planted partition model
• Algorithms for graph partitioning on the planted partition model
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Combinatorial statistics and the sciences
• Bounds on the bisection width for random \(d\)-regular graphs

This page was built for publication: The Metropolis algorithm for graph bisection

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