Dynamic programming optimization over random data: The scaling exponent for near-optimal solutions

A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over A ⊆ {1, 2,⋯, n}, the objective function |A| - Σ i ξ i 1 (i ∈ A, i + 1 ∈ A) for given ξi > 0. This problem, with random (ξi), provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions difiering from the optimal solution in a small proportion δ of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order δ 2 but not of smaller order. We conjecture this relationship holds widely in the context of dynamic prog amming over random data, and Monte Carlo simulations for the Kauffman-Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in [D. J. Aldous and A. G. Percus, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 11211-11215] of relating such scaling exponents to the algorithmic difficulty of optimization problems. © 2009 Society for Industrial and Applied Mathematics