Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions

Simple item page
dc.creatorAldous, David J.
dc.creatorBordenave, Charles
dc.creatorLelarge, Marc
dc.date2007-10-03
dc.date.accessioned2026-07-07T08:33:47Z
dc.date.available2026-07-07T08:33:47Z
dc.descriptionA very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over sets A in {1,2,...,n}, the objective function |A| - \sum_i ξ_i 1(i \in A,i+1 \in 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 differing 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 smaller order. We conjecture this relationship holds widely in the context of dynamic programming 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 Aldous-Percus (2003) of relating such scaling exponents to the algorithmic difficulty of optimization problems.
dc.description35 pages
dc.identifierhttps://arxiv.org/abs/0710.0857
dc.identifierhttp://arxiv.org/abs/0710.0857
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/139253
dc.subjectProbability
dc.subjectOptimization and Control
dc.subject68Q25, 90C39, 60J05.
dc.titleDynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions
dc.typetext

Files

Collections

arXiv