Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks

DOI10.1007/s10479-012-1199-xzbMath1268.90123OpenAlexW1970573563MaRDI QIDQ1945076

Alexander Zadorojniy, Guy Even

Publication date: 2 April 2013

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-012-1199-x

zbMATH Keywords

simplex algorithmMarkov decision processcontrolled random walkscontrolled queuesGass-Saaty shadow-vertex pivoting rule

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Markov and semi-Markov decision processes (90C40) Extreme-point and pivoting methods (90C49)

Related Items (2)

Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ On the reduction of total‐cost and average‐cost MDPs to discounted MDPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Pivot rules for linear programming: A survey on recent theoretical developments
• On the \(\epsilon\)-perturbation method for avoiding degeneracy
• Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
• Linear Programming and Sequential Decisions
• On Sequential Decisions and Markov Chains
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Technical Note—An Equivalence Between Continuous and Discrete Time Markov Decision Processes
• A Strongly Polynomial Algorithm for Controlled Queues
• Smoothed analysis of algorithms
• Linear Programming in Linear Time When the Dimension Is Fixed
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• Control Techniques for Complex Networks
• On queueing systems with variable service capacities
• A New Complexity Result on Solving the Markov Decision Problem

This page was built for publication: Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks