Search papers, labs, and topics across Lattice.
This paper investigates the convergence behavior of optimization algorithms for hard combinatorial problems, particularly focusing on the finite-size dynamics across varying difficulty regimes. The authors find that while algorithms eventually reach theoretical performance bounds, the convergence is notably slow, especially in intermediate regimes where local algorithms can outperform asymptotic predictions. These insights highlight the importance of sophisticated algorithmic design, as practical performance can significantly deviate from theoretical expectations in constrained scenarios.
Local algorithms can outperform theoretical predictions in constrained optimization scenarios, revealing a critical gap between finite and asymptotic performance.
Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as a powerful framework for understanding typical algorithmic performance beyond worst-case guarantees. A substantial body of work has established negative results: for sufficiently hard instances (often controlled by the underlying graph connectivity/constraints density), no known polynomial-time algorithm can significantly outperform naive heuristics in the double asymptotic limit where both problem size and constraints density tend to infinity. We revisit this picture by studying the finite-size behavior of some optimization algorithms across easy, intermediate, and hard regimes. Through rigorous analysis of large-graph asymptotics combined with numerical experiments on canonical problems (maximum independent set and maximum $K$-SAT), we demonstrate that while algorithms do eventually converge to theoretically predicted bounds, this convergence can be remarkably slow. In the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-constraint-density limit. This gap between finite-regime and asymptotic behavior has important practical implications: sophisticated algorithmic design remains crucial even when asymptotic theory predicts inevitable failure.
