The Metropolis algorithm for graph bisection
From MaRDI portal
Publication:1383365
DOI10.1016/S0166-218X(97)00133-9zbMath0932.60079OpenAlexW2024281442MaRDI QIDQ1383365
Gregory B. Sorkin, Mark R. 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
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov and semi-Markov decision processes (90C40)
Related Items
A deterministic annealing algorithm for approximating a solution of the min-bisection problem, Unnamed Item, Bounds on the bisection width for random \(d\)-regular graphs, Are Stable Instances Easy?, A landscape-based analysis of fixed temperature and simulated annealing, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Find Your Place: Simple Distributed Algorithms for Community Detection, Combinatorial statistics and the sciences, Choosing the right algorithm with hints from complexity theory, Asymptotic mutual information for the balanced binary stochastic block model, Hybridizing evolutionary algorithms with variable-depth search to overcome local optima, Step-by-step community detection in volume-regular graphs, Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery, Reconstruction and estimation in the planted partition model, Graph Partitioning via Adaptive Spectral Techniques, How to escape local optima in black box optimisation: when non-elitism outperforms elitism, Finding most likely solutions, Consistent nonparametric estimation for heavy-tailed sparse graphs, Runtime analysis of a simple ant colony optimization algorithm, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Distributed community detection in dynamic graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- The effect of the density of states on the Metropolis algorithm
- Efficient simulated annealing on fractal energy landscapes
- Survival time of a random graph
- Some simplified NP-complete graph problems
- Biased random walks
- The solution of some random NP-hard problems in polynomial expected time
- Approximating the Permanent
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Convergence and finite-time behavior of simulated annealing
- Cooling Schedules for Optimal Annealing
- Markov Chains with Rare Transitions and Simulated Annealing
- Large Cliques Elude the Metropolis Process
- Average-case analysis of algorithms for matchings and related problems
- The time complexity of maximum matching by simulated annealing
