2026-07-26T19:28:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24413 2025-12-12T15:01:37Z ddc:004 open_access

Time Lower Bounds for the Metropolis Process and Simulated Annealing Chen, Zongchen Mikulincer, Dan Reichman, Daniel Wein, Alexander S. Metropolis Process Simulated Annealing Independent Set The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any ε ∈ (0,1) there are n-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio Ω(1/n^{1-ε}) is exponentially small. Our lower bounds extend to graphs of constant average degree d, illustrating the failure of MP to achieve an approximation ratio of Ω(log(d)/d) in polynomial time. In some cases, our lower bounds apply even when the temperature is chosen adaptively. Finally, we prove exponential-time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zongchen Chen and Dan Mikulincer and Daniel Reichman and Alexander S. Wein 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.47 urn:nbn:de:0030-drops-244138 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode