{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T21:27:40Z","timestamp":1694640460464},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s10479-012-1199-x","type":"journal-article","created":{"date-parts":[[2012,7,31]],"date-time":"2012-07-31T06:58:22Z","timestamp":1343717902000},"page":"159-167","source":"Crossref","is-referenced-by-count":1,"title":["Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks"],"prefix":"10.1007","volume":"201","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Zadorojniy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,8,1]]},"reference":[{"key":"1199_CR1","series-title":"Contemporary mathematics","volume-title":"Deformed products and maximal shadows of polytopes","author":"N. Amenta","year":"1996","unstructured":"Amenta, N., & Ziegler, G. M. (1996). Advances in discrete and computational geometry. In Contemporary mathematics: Vol.\u00a0223. Deformed products and maximal shadows of polytopes. Providence: Am. Math. Soc."},{"key":"1199_CR2","first-page":"42","volume-title":"Innovations in computer science","author":"M. Barasz","year":"2010","unstructured":"Barasz, M., & Vempala, S. (2010). A new approach to strongly polynomial linear programming. In Innovations in computer science (pp.\u00a042\u201348)."},{"issue":"1","key":"1199_CR3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01917108","volume":"26","author":"K. H. Borgwardt","year":"1982","unstructured":"Borgwardt, K. H. (1982a). The average number of pivot steps required by the simplex-method is polynomial. Mathematical Methods of Operations Research, 26(1), 157\u2013177.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"3","key":"1199_CR4","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.7.3.441","volume":"7","author":"K. H. Borgwardt","year":"1982","unstructured":"Borgwardt, K. H. (1982). Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method. Mathematics of Operations Research, 7(3), 441\u2013462.","journal-title":"Mathematics of Operations Research"},{"key":"1199_CR5","first-page":"161","volume":"2","author":"G. Ghellinck de","year":"1960","unstructured":"de Ghellinck, G. (1960). Les problemes de decisions sequentielles. Cahiers Du Centre D\u2019\u00e9tudes de Recherche Op\u00e9rationnelle, 2, 161\u2013179.","journal-title":"Cahiers Du Centre D\u2019\u00e9tudes de Recherche Op\u00e9rationnelle"},{"issue":"1","key":"1199_CR6","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1287\/mnsc.10.1.98","volume":"10","author":"F. d\u2019Epenoux","year":"1963","unstructured":"d\u2019Epenoux, F. (1963). A probabilistic production and inventory problem. Management Science, 10(1), 98\u2013108.","journal-title":"Management Science"},{"issue":"1","key":"1199_CR7","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/mnsc.9.1.16","volume":"9","author":"C. Derman","year":"1962","unstructured":"Derman, C. (1962). On sequential decisions and markov chains. Management Science, 9(1), 16\u201324.","journal-title":"Management Science"},{"issue":"1\u20132","key":"1199_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/nav.3800020106","volume":"2","author":"S. Gass","year":"1955","unstructured":"Gass, S., & Saaty, T. (1955). The computational algorithm for the parametric objective function. Naval Research Logistics Quarterly, 2(1\u20132), 39\u201345.","journal-title":"Naval Research Logistics Quarterly"},{"key":"1199_CR9","volume-title":"Controlled queueing systems","author":"M. Y. Kitaev","year":"1995","unstructured":"Kitaev, M. Y., & Rykov, V. V. (1995). Controlled queueing systems. Boca Raton: CRC Press."},{"key":"1199_CR10","volume-title":"Queueing systems, Vol. I: Theory","author":"L. Kleinrock","year":"1975","unstructured":"Kleinrock, L. (1975). Queueing systems, Vol. I: Theory. New York: Wiley."},{"issue":"3","key":"1199_CR11","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/mnsc.6.3.259","volume":"6","author":"A. S. Manne","year":"1960","unstructured":"Manne, A. S. (1960). Linear programming and sequential decisions. Management Science, 6(3), 259\u2013267.","journal-title":"Management Science"},{"key":"1199_CR12","volume-title":"Understanding and using linear programming","author":"J. Matou\u0161ek","year":"2007","unstructured":"Matou\u0161ek, J., & G\u00e4rtner, B. (2007). Understanding and using linear programming. Berlin: Springer."},{"issue":"1","key":"1199_CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N. (1984). Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1), 114\u2013127.","journal-title":"Journal of the ACM"},{"key":"1199_CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/CCOL0521340446.006","volume-title":"Advances in economic theory: fifth world congress","author":"N. Megiddo","year":"1987","unstructured":"Megiddo, N. (1987). On the complexity of linear programming. In T. Bewley (Ed.), Advances in economic theory: fifth world congress (pp. 225\u2013268). Cambridge: Cambridge University Press."},{"issue":"6","key":"1199_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0167-6377(89)90014-X","volume":"8","author":"N. Megiddo","year":"1989","unstructured":"Megiddo, N., & Chandrasekaran, R. (1989). On the \u03b5-perturbation method for avoiding degeneracy. Operations Research Letters, 8(6), 305\u2013308.","journal-title":"Operations Research Letters"},{"key":"1199_CR16","volume-title":"Control techniques for complex networks","author":"S. P. Meyn","year":"2008","unstructured":"Meyn, S. P. (2008). Control techniques for complex networks. Cambridge: Cambridge University Press."},{"key":"1199_CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes: discrete stochastic dynamic programming","author":"M. L. Puterman","year":"1994","unstructured":"Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic programming. New York: Wiley."},{"key":"1199_CR18","volume-title":"Theory of linear and integer programming","author":"A. Schrijver","year":"1998","unstructured":"Schrijver, A. (1998). Theory of linear and integer programming. New York: Wiley."},{"issue":"3","key":"1199_CR19","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1287\/opre.27.3.616","volume":"27","author":"R. F. Serfozo","year":"1979","unstructured":"Serfozo, R. F. (1979). An equivalence between continuous and discrete time markov decision processes. Operations Research, 27(3), 616\u2013620.","journal-title":"Operations Research"},{"issue":"3","key":"1199_CR20","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D. A. Spielman","year":"2004","unstructured":"Spielman, D. A., & Teng, S. H. (2004). Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 385\u2013463.","journal-title":"Journal of the ACM"},{"issue":"3","key":"1199_CR21","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"E. Tardos","year":"1985","unstructured":"Tardos, E. (1985). A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3), 247\u2013255.","journal-title":"Combinatorica"},{"issue":"2","key":"1199_CR22","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E. (1986). A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2), 250\u2013256.","journal-title":"Operations Research"},{"issue":"1","key":"1199_CR23","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02096264","volume":"46","author":"T. Terlaky","year":"1993","unstructured":"Terlaky, T., & Zhang, S. (1993). Pivot rules for linear programming: a survey on recent theoretical developments. Annals of Operations Research, 46(1), 203\u2013233.","journal-title":"Annals of Operations Research"},{"key":"1199_CR24","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1109\/FOCS.2006.19","volume-title":"FOCS\u201906. 47th annual IEEE symposium on foundations of computer science, 2006","author":"R. Vershynin","year":"2006","unstructured":"Vershynin, R. (2006). Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. In FOCS\u201906. 47th annual IEEE symposium on foundations of computer science, 2006 (pp. 133\u2013142). New York: IEEE Press."},{"key":"1199_CR25","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1002\/nav.3800140105","volume":"14","author":"M. Yadin","year":"1967","unstructured":"Yadin, M., & Naor, P. (1967). On queueing systems with variable service capacities. Naval Research Logistics Quarterly, 14, 43\u201353.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"3","key":"1199_CR26","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1287\/moor.1050.0149","volume":"30","author":"Y. Ye","year":"2005","unstructured":"Ye, Y. (2005). A new complexity result on solving the Markov decision problem. Mathematics of Operations Research, 30(3), 733\u2013749.","journal-title":"Mathematics of Operations Research"},{"key":"1199_CR27","unstructured":"Ye, Y. (2010). The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Seminar, talk."},{"issue":"4","key":"1199_CR28","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1287\/moor.1110.0516","volume":"36","author":"Y. Ye","year":"2011","unstructured":"Ye, Y. (2011). The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36(4), 593\u2013603.","journal-title":"Mathematics of Operations Research"},{"key":"1199_CR29","unstructured":"Zadorojniy, A., & Even, G. Hyperbolic behavior of occupation measures between neighboring policies in CMDPs. http:\/\/www.eng.tau.ac.il\/~sasha\/ ."},{"issue":"4","key":"1199_CR30","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1287\/moor.1090.0415","volume":"34","author":"A. Zadorojniy","year":"2009","unstructured":"Zadorojniy, A., Even, G., & Shwartz, A. (2009). A strongly polynomial algorithm for controlled queues. Mathematics of Operations Research, 34(4), 992\u20131007.","journal-title":"Mathematics of Operations Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-012-1199-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-012-1199-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-012-1199-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T09:18:47Z","timestamp":1562059127000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-012-1199-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["1199"],"URL":"https:\/\/doi.org\/10.1007\/s10479-012-1199-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,1]]}}}