The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
Abstract
In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program—the ALP—that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m≪M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by exact solution of the ALP? We show that, given an idealized sampling distribution and appropriate constraints on the K variables, m can be chosen independently of M and need grow only as a polynomial in K. We interpret this result in a context involving controlled queueing networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5086 · Cited by 3,515
Neuro-Dynamic Programming: NDP
Bertsekas, D. P. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_333 · Cited by 1,466
The Linear Programming Approach to Approximate Dynamic Programming
de Farias, D. P., & Van Roy, B. (2003) · Operations Research · doi:10.1287/opre.51.6.850.24925 · Cited by 687
Self-citationUncertain convex programs: randomized solutions and confidence levels
Calafiore, G., & Campi, M. C. (2005) · Mathematical Programming · doi:10.1007/s10107-003-0499-y · Cited by 659
Central Limit Theorems for Empirical Measures
Dudley, R. M. (1978) · The Annals of Probability · doi:10.1214/aop/1176995384 · Cited by 571
Efficient Solution Algorithms for Factored MDPs
Guestrin, C., Koller, D., Parr, R., & Venkataraman, S. (2003) · Cited by 384
Generalized polynomial approximations in Markovian decision processes
Schweitzer, P. J., & Seidmann, A. (1985) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(85)90317-8 · Cited by 330
Las Vegas algorithms for linear and integer programming when the dimension is small
Clarkson, K. L. (1995) · Journal of the ACM · doi:10.1145/201019.201036 · Cited by 223
Efficient Solution Algorithms for Factored MDPs
Guestrin, C., Koller, D., Parr, R., & Venkataraman, S. (2003) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1000 · Cited by 169
Equivalence of models for polynomial learnability
Haussler, D. H., Kearns, M. J., Littlestone, N., & Warmuth, M. K. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90042-z · Cited by 134
Cited by
Delage, E., & Ye, Y. (2010) · Operations Research · doi:10.1287/opre.1090.0741 · Cited by 1,893
Convex Approximations of Chance Constrained Programs
Nemirovski, A., & Shapiro, A. (2007) · SIAM Journal on Optimization · doi:10.1137/050622328 · Cited by 1,160
Algorithms for Reinforcement Learning
Szepesvári, C. (2010) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.1007/978-3-031-01551-9 · Cited by 1,049
Uncertain convex programs: randomized solutions and confidence levels
Calafiore, G., & Campi, M. C. (2005) · Mathematical Programming · doi:10.1007/s10107-003-0499-y · Cited by 659
The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
Campi, M. C., & Garatti, S. (2008) · SIAM Journal on Optimization · doi:10.1137/07069821x · Cited by 560
Metadata
- Authors
- de Farias, D. P., & Van Roy, B.
- Venue
- Mathematics of Operations Research
- Published
- 2004-08
- Volume
- 29
- Issue
- 3
- Pages
- 462-478
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2158479468
- Cited by
- 373
- References
- 11
- FWCI
- 16.67
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming. https://app.cochat.ai/papers/10.1287/moor.1040.0094
- The paper
- de Farias, D. P., & Van Roy, B. (2004). On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming. Mathematics of Operations Research. https://doi.org/10.1287/moor.1040.0094
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
