Mathematics – Probability
Scientific paper
2007-10-03
Mathematics
Probability
35 pages
Scientific paper
A 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 \xi_i 1(i \in A,i+1 \in A) for given \xi_i > 0. This problem, with random (\xi_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 \delta of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order \delta^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.
Aldous David J.
Bordenave Charles
Lelarge Marc
No associations
LandOfFree
Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-286162