Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem

DOI10.1007/s00453-023-01135-xarXiv2204.02097MaRDI QIDQ6185935

Carsten Witt, Benjamin Doerr, Amirhossein Rajabi

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.02097

zbMATH Keywords

simulated annealingtheoryminimum spanning treesapproximation schemeruntime analysis

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Optimization by Simulated Annealing
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Maximum of k-th maximal spanning trees of a weighted graph
• Revisiting simulated annealing: a component-based analysis
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Adaptive drift analysis
• Multiplicative drift analysis
• Exponential upper bounds for the runtime of randomized search heuristics
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• The time complexity of maximum matching by simulated annealing
• Theory of Evolutionary Computation
• STACS 2005
• Automata, Languages and Programming
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item