Accession Number ADA564449
Title Optimization Algorithms and Equilibrium Analysis for Dynamic Resource Allocation.
Publication Date Jan 2012
Media Count 7p
Personal Author Y. Ye
Abstract We consider optimization and equilibrium models and algorithms for dynamic resource allocation. The most important accomplishment would be the paper: The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate, where I proved that the classic policy-iteration method (Howard 1960), including the Simplex method (Dantzig 1947) with the most-negative-reduced-cost pivoting rule, is a strongly polynomial-time exact algorithm for solving the Markov decision problem (MDP) exactly with any fixed discount factor. Markov decision process (e.g., Shapley, 1953) is arguably one of the most widely used decision models and methodologies in practice, as a celebrated example to showcase the power of optimization to help making sensible decisions in a complex system and stochastic environment. And the two methods are the most used methods but their theoretical complexities were open before this result. We also explore an online resource allocation in a set of research publications, including prediction market, Internet auction, and etc.
Keywords Algorithms
Decision making
Decision theory
Markov processes
Mathematical models
Online systems
Resource management
Simplex method
Stochastic processes

Source Agency Non Paid ADAS
NTIS Subject Category 72F - Statistical Analysis
Corporate Author Stanford Univ., CA.
Document Type Technical report
Title Note Final rept. 15 Apr 2009-30 Nov 2012.
NTIS Issue Number 1303
Contract Number FA9550-09-1-0306

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader