{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T04:04:24Z","timestamp":1648958664868},"reference-count":53,"publisher":"Elsevier","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1016\/s0169-7161(05)80130-0","type":"book-chapter","created":{"date-parts":[[2005,4,18]],"date-time":"2005-04-18T15:58:53Z","timestamp":1113839933000},"page":"169-200","source":"Crossref","is-referenced-by-count":0,"title":["6 Algorithms and complexity for markov processes"],"prefix":"10.1016","author":[{"given":"Ravi","family":"Varadarajan","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0169-7161(05)80130-0_bib1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1137\/0211047","article-title":"Finding the cyclic index of an irreducible, nonnegative matrix","volume":"11","author":"Atallah","year":"1982","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib3","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1145\/828.322449","article-title":"Graph problems on a mesh-connected processor array","volume":"31","author":"Atallah","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/S0169-7161(05)80130-0_bib4","series-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"10.1016\/S0169-7161(05)80130-0_bib5","series-title":"Proc. 25th IEEE Conf. on Decision and Control","first-page":"1840","article-title":"Dynamic aggregation methods for discounted Markovian decision problems","author":"Bertsekas","year":"1986"},{"key":"10.1016\/S0169-7161(05)80130-0_bib6","series-title":"Parallel and Distributed Computation \u2014 Numerical Methods","author":"Bertsekas","year":"1989"},{"key":"10.1016\/S0169-7161(05)80130-0_bib7","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1214\/aoms\/1177700285","article-title":"Discounted dynamic programming","volume":"36","author":"Blackwell","year":"1965","journal-title":"Ann. Math. Statist."},{"key":"10.1016\/S0169-7161(05)80130-0_bib8","article-title":"Maximal parallelism in matrix multiplication","author":"Chandra","year":"1976"},{"key":"10.1016\/S0169-7161(05)80130-0_bib9","series-title":"Proc. 3rd Ann. ACM Sympos. on Theory of Computing","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/S0169-7161(05)80130-0_bib10","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","article-title":"A taxonomy of problems with fast parallel algorithms","volume":"64","author":"Cook","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/S0169-7161(05)80130-0_bib11","series-title":"Proc. 19th Ann. ACM Sympos. on Theory of Computing","first-page":"1","article-title":"Matrix multiplication via arithmetic progressions","author":"Coppersmith","year":"1987"},{"key":"10.1016\/S0169-7161(05)80130-0_bib12","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","article-title":"Fast parallel matrix inversion algorithms","volume":"5","author":"Csanky","year":"1976","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0169-7161(05)80130-0_bib13","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","article-title":"Parallel matrix and graph algorithms","volume":"10","author":"Dekel","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0169-7161(05)80130-0_bib14","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1137\/0116038","article-title":"Multichain Markov renewal programs","volume":"16","author":"Denardo","year":"1968","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0169-7161(05)80130-0_bib15","article-title":"Sur un probl\u00e8me de production et de stockage dans l'al\u00e9atoire","volume":"14","author":"D'Epenoux","year":"1960","journal-title":"Rev. Francaise Informat. Rech. Op\u00e9r."},{"key":"10.1016\/S0169-7161(05)80130-0_bib16","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/mnsc.9.1.16","article-title":"On sequential decisions and Markov chains","volume":"9","author":"Derman","year":"1962","journal-title":"Management Sci."},{"key":"10.1016\/S0169-7161(05)80130-0_bib17","series-title":"Finite state Markovian Decision Processes","author":"Derman","year":"1970"},{"key":"10.1016\/S0169-7161(05)80130-0_bib18","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/S0169-7161(05)80130-0_bib19","series-title":"Graph Algorithms","author":"Even","year":"1979"},{"key":"10.1016\/S0169-7161(05)80130-0_bib20","volume":"Vol. I","author":"Feller","year":"1968"},{"issue":"6","key":"10.1016\/S0169-7161(05)80130-0_bib21","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest path","volume":"5","author":"Floyd","year":"1962","journal-title":"Comm. ACM"},{"key":"10.1016\/S0169-7161(05)80130-0_bib22","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1145\/364063.364082","article-title":"An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix","volume":"11","author":"Fox","year":"1968","journal-title":"Comm. ACM"},{"key":"10.1016\/S0169-7161(05)80130-0_bib23","series-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0169-7161(05)80130-0_bib24","series-title":"Proc. 10th Ann. ACM Sympos. on Theory of Computing","first-page":"89","article-title":"A unified approach to models of synchronous parallel machines","author":"Goldschlager","year":"1978"},{"key":"10.1016\/S0169-7161(05)80130-0_bib25","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1287\/mnsc.25.4.352","article-title":"Linear programming and Markov decision chains","volume":"25","author":"Hordijk","year":"1979","journal-title":"Management Sci."},{"issue":"2","key":"10.1016\/S0169-7161(05)80130-0_bib26","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1287\/moor.9.2.276","article-title":"Constrained undiscounted stochastic dynamic programming","volume":"9","author":"Hordijk","year":"1984","journal-title":"J. Math. Oper. Res."},{"key":"10.1016\/S0169-7161(05)80130-0_bib27","series-title":"Dynamic Programming and Markov Processes","author":"Howard","year":"1960"},{"key":"10.1016\/S0169-7161(05)80130-0_bib28","article-title":"Linear Programming and Finite Markovian Control Problems","volume":"Vol. 148","author":"Kallenberg","year":"1983"},{"key":"10.1016\/S0169-7161(05)80130-0_bib29","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF02579150","article-title":"A new polynomial time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/S0169-7161(05)80130-0_bib30","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S0169-7161(05)80130-0_bib31","series-title":"Finite Markov Chains","author":"Kemeny","year":"1976"},{"key":"10.1016\/S0169-7161(05)80130-0_bib32","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachian","year":"1979","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/S0169-7161(05)80130-0_bib33","series-title":"Lecture notes delivered at the Matematisk Institutt of the University of Oslo, Norway, 1972\u201373","author":"Knuth","year":"1973"},{"key":"10.1016\/S0169-7161(05)80130-0_bib34","series-title":"Analysis and Design of Parallel Algorithms \u2014 Arithmetic and Matrix Problems","author":"Lakshmivarahan","year":"1990"},{"key":"10.1016\/S0169-7161(05)80130-0_bib35","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/mnsc.6.3.259","article-title":"Linear programming and sequential decisions","volume":"6","author":"Manne","year":"1960","journal-title":"Management Sci."},{"key":"10.1016\/S0169-7161(05)80130-0_bib36","series-title":"Algorithmic Graph Theory","author":"McHugh","year":"1990"},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib37","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1287\/moor.12.3.441","article-title":"The complexity of Markov decision processes","volume":"12","author":"Papadimitriou","year":"1987","journal-title":"J. Math. Oper. Res."},{"key":"10.1016\/S0169-7161(05)80130-0_bib38","series-title":"Proc. 20th IEEE Sympos. on the Foundations of Computing Science","first-page":"307","article-title":"On simultaneous resource bounds","author":"Pippenger","year":"1979"},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib39","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/2514.2515","article-title":"Parallel graph algorithms","volume":"16","author":"Quinn","year":"1984","journal-title":"ACM Comput. Surveys"},{"issue":"2","key":"10.1016\/S0169-7161(05)80130-0_bib40","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0207020","article-title":"Parallel computations in graph theory","volume":"2","author":"Reghbati","year":"1978","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0169-7161(05)80130-0_bib41","series-title":"Applied Probability Models with Optimization Applications","author":"Ross","year":"1970"},{"key":"10.1016\/S0169-7161(05)80130-0_bib42","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1287\/opre.37.5.780","article-title":"Markov decision processes with sample path constraints: The communicating case","volume":"37","author":"Ross","year":"1989","journal-title":"Oper. Res."},{"issue":"1","key":"10.1016\/S0169-7161(05)80130-0_bib43","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1287\/moor.16.1.195","article-title":"Multichain Markov decision processes with a sample path constraint","volume":"16","author":"Ross","year":"1991","journal-title":"J. Math. Oper. Res."},{"issue":"2","key":"10.1016\/S0169-7161(05)80130-0_bib44","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/321160.321170","article-title":"Computability of recursive functions","volume":"10","author":"Shepherdson","year":"1963","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib45","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","article-title":"On parallel searching","volume":"14","author":"Snir","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0169-7161(05)80130-0_bib46","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numer. Math."},{"key":"10.1016\/S0169-7161(05)80130-0_bib47","series-title":"Proc. Conf. on Foundations of Computer Science","first-page":"49","article-title":"The asymptotic spectrum of tensors and the exponent of matrix multiplication","author":"Strassen","year":"1986"},{"issue":"2","key":"10.1016\/S0169-7161(05)80130-0_bib48","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0169-7161(05)80130-0_bib49","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"42","author":"Turing","year":"1936"},{"key":"10.1016\/S0169-7161(05)80130-0_bib50","series-title":"Markov Decision Theory","first-page":"1","article-title":"Markov decision processes with unbounded rewards","volume":"Vol. 93","author":"Van Nunen","year":"1977"},{"key":"10.1016\/S0169-7161(05)80130-0_bib51","article-title":"Computational complexity analysis of Markovian reconfiguration models","author":"Varadarajan","year":"1990"},{"issue":"3","key":"10.1016\/S0169-7161(05)80130-0_bib52","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1007\/BF01931660","article-title":"Partitioning multi-edge graphs","volume":"30","author":"Varadarajan","year":"1990","journal-title":"BIT"},{"key":"10.1016\/S0169-7161(05)80130-0_bib53","article-title":"The complexity of parallel computations","author":"Wyllie","year":"1979"}],"container-title":["Handbook of Statistics","Computational Statistics"],"original-title":[],"deposited":{"date-parts":[[2019,1,26]],"date-time":"2019-01-26T21:54:34Z","timestamp":1548539674000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0169716105801300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"references-count":53,"URL":"https:\/\/doi.org\/10.1016\/s0169-7161(05)80130-0","relation":{},"ISSN":["0169-7161"],"issn-type":[{"value":"0169-7161","type":"print"}],"subject":[],"published":{"date-parts":[[1993]]}}}