An exponential lower bound for Zadeh's pivot rule
From MaRDI portal
Publication:6038661
DOI10.1007/s10107-022-01848-xarXiv1911.01074WikidataQ114228488 ScholiaQ114228488MaRDI QIDQ6038661
Yann Disser, Oliver Friedmann, Alexander V. Hopp
Publication date: 2 May 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.01074
Markov decision processes; parity games; lower bound; simplex method; policy iteration; strategy improvement; Zadeh's rule
68Q25: Analysis of algorithms and problem complexity
90C05: Linear programming
90C40: Markov and semi-Markov decision processes