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

DOI10.1007/S00453-023-01135-XMaRDI QIDQ6185935zbMATH OpenFDO

Authors Benjamin Doerr, Amirhossein Rajabi, Carsten Witt

Publication date 9 January 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

Abstract: We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (2005). More precisely, denoting by $n,m,w_{max}$, and $w_{min}$ the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature $T_{0}ge{w}_{max}$ and multiplicative cooling schedule with factor $1-1/ell$, where $ell=omega(mnln(m))$, with probability at least $1-1/m$ computes in time $O(ell(lnln(ell)+ln(T_0/w_{min})))$ a spanning tree with weight at most $1+kappa$ times the optimum weight, where $1+kappa=frac(1+o(1))ln(ellm)ln(ell)-ln(mnln(m))$. Consequently, for any $epsilon>0$, we can choose $ell$ in such a way that a $(1+epsilon)$-approximation is found in time $O((mnln(n){)}^{1+1/epsilon+o(1)}(lnlnn+ln(T_0/w_{min})))$ with probability at least $1-1/m$. In the special case of so-called $(1+epsilon)$-separated weights, this algorithm computes an optimal solution (again in time $O((mnln(n){)}^{1+1/epsilon+o(1)}(lnlnn+ln(T_0/w_{min})))$), which is a significant speed-up over Wegener's runtime guarantee of $O(m^{8+8/epsilon})$.

Cites work

• scientific article; zbMATH DE number 1962832 (Why is no real title available?)
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• Adaptive drift analysis
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Automata, Languages and Programming
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Dynamic parameter control in simple evolutionary algorithms
• Exponential upper bounds for the runtime of randomized search heuristics
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• Inequalities on the Lambert \(W\) function and hyperpower function
• Maximum of k-th maximal spanning trees of a weighted graph
• Multiplicative drift analysis
• Optimization by simulated annealing
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Revisiting simulated annealing: a component-based analysis
• STACS 2005
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• The time complexity of maximum matching by simulated annealing
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited in

(1)

• A theoretical investigation of termination criteria for evolutionary algorithms

This page was built for publication: Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem

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