Algorithmic thresholds in combinatorial optimization depend on the time scaling

Abstract

In the last decades, many efforts have focused on analyzing typical-case hardness in optimization and inference problems. Some recent work has pointed out that polynomial algorithms exist, running with a time that grows more than linearly with the system size, which can do better than linear algorithms, finding solutions to random problems in a wider range of parameters. However, a theory for polynomial and superlinear algorithms is in general lacking. In this paper, we examine the performance of the Simulated Annealing algorithm, a standard, versatile, and robust choice for solving optimization and inference problems, in the prototypical random $K$-Sat problem. For the first time, we show that the algorithmic thresholds depend on the time scaling of the algorithm with the size of the system. Indeed, one can identify not just one, but different thresholds for linear, quadratic, cubic regimes (and so on). This observation opens new directions in studying the typical case hardness in optimization problems.

References in corpus (14)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Circumspect descent prevails in solving random constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Unveiling the structure of wide flat minima in neural networks
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Quenches in the Sherrington-Kirkpatrick model
• Optimization of the dynamic transition in the continuous coloring problem
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold

Cited by in corpus (1)

• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties