Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions

DOI10.1137/070709037zbMath1193.68123arXiv0710.0857OpenAlexW2043317253MaRDI QIDQ3654380

Marc Lelarge, David J. Aldous, Charles Bordenave

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0710.0857

zbMATH Keywords

weak convergencedynamic programmingscaling exponentanalysis of algorithmnear-optimal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete-time Markov processes on general state spaces (60J05) Dynamic programming (90C39)

Related Items (2)

Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ The planted matching problem: phase transitions and exact results

This page was built for publication: Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions