On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems
Authors: Ali Hussaini Umar, Jean Barbier, Matthieu Jonckheere, Manuel Sáenz
Organizations: SISSA, Trieste, Italy. · International Center for Theoretical Physics, Trieste, Italy. · LAAS–CNRS, Toulouse, France. · Universidad de San Andrés, Argentina.
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.
Figures & tables
Figure 1: Average performance ratio of the degree greedy (DG), static degree greedy (SDG), and max-product (MP) algorithms as a function of mean degree λ . The solid blue line represents the theoretical asymptotic performance of SDG, while the blue dots with error bars represent its finite-size simulation results. The red dashed line represents the DG simulation results. The orange dots with error bars represent the MP numerical results, and the orange diamonds represent the population dynamics (PD) predictions. For all three algorithms, the finite-size performance remains above the 1/2 asymptotic threshold. This provides comprehensive (both theoretical and numerical) evidence that local algorithms can produce independent sets of size exceeding the theoretical threshold in sparse Erdős-Rényi graphs even for practically large sizes and degree means. For DG and SDG, the results are averaged across 10 realizations of Erdős-Rényi graphs G(n,λ/n) with n=105 , while the MP results are averaged over 25 independent realizations of the same graph ensemble.
Figure 2: Convergence of the performance ratio of static degree greedy (SDG) towards the half-bound threshold . The plot displays RSDG(λ) given by ( 11 ), interpreted as a natural performance lower bound for a large class of non-trivial algorithms for MIS, on Erdős-Rényi graphs G(n,λ/n) as a function of the degree λ in the limit of large n . The blue solid line represents the convergence of the theoretical results of SDG, while the red dashed line represents a power law fit for large values of λ .
Figure 3: Heatmap of the performance ratios of the degree greedy (DG) and static degree greedy (SDG) algorithms on Erdős-Rényi graphs G(n,λ/n) . The left panel presents the results for DG, while the right panel shows the results for SDG. Both greedy algorithms achieve high ratios (above 1/2 ) for sparser graphs, but the ratios fall below 1/2 for denser graphs.
Figure 4: Asymptotic performance of RC for Max K -SAT. On the left, we compare the ratio of satisfied clauses as a function of the clause density ( α=m/n ) of RC on simulations ( n=1000 , ten simulations for each point) with the predictions from the limit equations for K=4 . Here we can appreciate that this ratio converges asymptotically, as argued, to the random assignment performance. On the right, asymptotic ratio of satisfied clauses as a function of clause density ( α=m/n ) for different values of K . These simulations suggest that the convergence to the limit follows a similar rate of decay for all K considered. In both graphs, the asymptotic performance of random assignments are plotted as dashed horizontal blue lines.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Department of Computing Sciences, Bocconi University, Milan, Italy · Bocconi Institute for Data Science and Analytics (BIDSA) · Department of Physics and Astronomy and INFN, University of Florence +4
Max Planck Institute for the Physics of Complex Systems, Nöthnitzer Str. 38, 01187 Dresden, Germany · Institute of Theoretical Physics, Technische Universität Dresden and Würzburg-Dresden Cluster of Excellence ctd.qmat, 01062 Dresden, Germany