Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
type: Item
instance of: scholarly article
title: Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
zbMATH Open document ID: 1268.90123
author: Guy Even
author: Alexander Zadorojniy
published in: Annals of Operations Research
publication date: 2013-04-02T00:00:00Z
Mathematics Subject Classification ID: 90C40
Mathematics Subject Classification ID: 90C49
Mathematics Subject Classification ID: 90B22
zbMATH DE Number: 6149323
zbMATH Keywords: Markov decision process
zbMATH Keywords: controlled queues
zbMATH Keywords: controlled random walks
zbMATH Keywords: simplex algorithm
zbMATH Keywords: Gass-Saaty shadow-vertex pivoting rule
MaRDI profile type: Publication
full work available at URL: s10479-012-1199-x
OpenAlex ID: W1970573563
cites work: The Average number of pivot steps required by the Simplex-Method is polynomial
cites work: Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
cites work: Q3270185
cites work: On sequential decisions and Markov chains
cites work: Q4331806
cites work: Q4101255
cites work: Linear programming and sequential decisions
cites work: Linear Programming in Linear Time When the Dimension Is Fixed
cites work: Q3976517
cites work: On the \(\epsilon\)-perturbation method for avoiding degeneracy
cites work: Control Techniques for Complex Networks
cites work: Q4315289
cites work: Q4221106
cites work: Technical Note—An Equivalence Between Continuous and Discrete Time Markov Decision Processes
cites work: Smoothed analysis of algorithms
cites work: A strongly polynomial minimum cost circulation algorithm
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Pivot rules for linear programming: A survey on recent theoretical developments
cites work: On queueing systems with variable service capacities
cites work: A New Complexity Result on Solving the Markov Decision Problem
cites work: The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
cites work: A Strongly Polynomial Algorithm for Controlled Queues
DOI: 10.1007/S10479-012-1199-X
description: scientific article; zbMATH DE number 6149323