{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:52:00Z","timestamp":1782867120225,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_50","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"552-563","source":"Crossref","is-referenced-by-count":74,"title":["Stochastic Shortest Paths Via Quasi-convex Maximization"],"prefix":"10.1007","author":[{"given":"Evdokia","family":"Nikolova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan A.","family":"Kelner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"Brand","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"50_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/11602613_68","volume-title":"Algorithms and Computation","author":"H. Ackermann","year":"2005","unstructured":"Ackermann, H., Newman, A., R\u00f6glin, H., V\u00f6cking, B.: Decision making based on approximate and smoothed pareto curves. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 675\u2013684. Springer, Heidelberg (2005)"},{"key":"50_CR2","volume-title":"Dynamic Programming and Optimal Control","author":"D. Bertsekas","year":"2001","unstructured":"Bertsekas, D.: Dynamic Programming and Optimal Control, 2nd edn., vol.\u00a0II. Athena Scientific, Belmont (2001)","edition":"2"},{"key":"50_CR3","unstructured":"Boyan, J., Mitzenmacher, M.: Improved results for route planning in stochastic transportation networks. In: Proc. of Symposium of Discrete Algorithms (2001)"},{"key":"50_CR4","unstructured":"Carstensen, P.: The complexity of some problems in parametric linear and combinatorial programming. Ph.D. Thesis, Mathematics Dept., U. of Michigan, Ann Arbor, Mich. (1983)"},{"key":"50_CR5","doi-asserted-by":"crossref","unstructured":"Dean, B., Goemans, M., Vondrak, J.: Approximating the stochastic knapsack: The benefit of adaptivity. In: Proceedings of FOCS, pp. 208\u2013217 (2004)","DOI":"10.1109\/FOCS.2004.15"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Fan, Y., Kalaba, R., Moore, I.J.E.: Arriving on time. Journal of Optimization Theory and Applications (forthcoming)","DOI":"10.1007\/s10957-005-7498-5"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proceedings of the 40th Symposium on Foundations of Computer Science (1999)","DOI":"10.1109\/SFFCS.1999.814632"},{"key":"50_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0015-5","volume-title":"Introduction to Global Optimization","author":"R. Horst","year":"2000","unstructured":"Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"50_CR9","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D. Karger","year":"1997","unstructured":"Karger, D., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica\u00a018, 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Spielman, D.A.: A randomized polynomial-time simplex algorithm for linear programming. Electronic Colloquium on Computational Complexity\u00a0(156) (2005)","DOI":"10.1145\/1132516.1132524"},{"issue":"1","key":"50_CR11","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/S0097539797329142","volume":"30","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J., Rabani, Y., Tardos, \u00c9.: Allocating bandwidth for bursty connections. SIAM Journal on Computing\u00a030(1), 191\u2013217 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR12","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/358172.358406","volume":"26","author":"R.P. Loui","year":"1983","unstructured":"Loui, R.P.: Optimal paths in graphs with stochastic or multidimentional weights. Communications of the ACM\u00a026, 670\u2013676 (1983)","journal-title":"Communications of the ACM"},{"key":"50_CR13","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1287\/trsc.34.2.198.12304","volume":"34","author":"E.D. Miller-Hooks","year":"2000","unstructured":"Miller-Hooks, E.D., Mahmassani, H.S.: Least expected time paths in stochastic, time-varying transportation networks. Transportation Science\u00a034, 198\u2013215 (2000)","journal-title":"Transportation Science"},{"issue":"4","key":"50_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0305-0548(85)90034-6","volume":"12","author":"P. Mirchandani","year":"1985","unstructured":"Mirchandani, P., Soroush, H.: Optimal paths in probabilistic networks: A case with temporary preferences. Computers and Operations Research\u00a012(4), 365\u2013381 (1985)","journal-title":"Computers and Operations Research"},{"key":"50_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0377-2217(91)90094-C","volume":"53","author":"J. Mote","year":"1991","unstructured":"Mote, J., Murthy, I., Olson, D.: A parametric approach to solving bicriterion shortest path problems. European Journal of Operational Research\u00a053, 81\u201392 (1991)","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"50_CR16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1006\/jcss.2001.1766","volume":"63","author":"K. Mulmuley","year":"2001","unstructured":"Mulmuley, K., Shah, P.: A lower bound for the shortest path problem. Journal of Computer and System Sciences\u00a063(2), 253\u2013267 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR17","unstructured":"Nikolova, E., Brand, M., Karger, D.R.: Optimal route planning under uncertainty. In: Proceedings of International Conference on Automated Planning and Scheduling (2006)"},{"key":"50_CR18","unstructured":"Nikolova, E., Kelner, J.A.: On the hardness and smoothed complexity of low-rank quasi-concave minimization (May 2006) (manuscript)"},{"key":"50_CR19","doi-asserted-by":"crossref","unstructured":"Pallottino, S., Scutella, M.G.: Shortest path algorithms in transportation models: Classical and innovative aspects. Technical Report TR-97-06, Universita di Pisa Dipartimento di Informatica, Pisa, Italy (1997)","DOI":"10.1007\/978-1-4615-5757-9_11"},{"key":"50_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theoretical Computer Science\u00a084, 127\u2013150 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"50_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"C.H. Papadimitriou","year":"1996","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. Journal of Computer and System Sciences\u00a053(2), 161\u2013170 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"50_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1002\/(SICI)1097-0037(199603)27:2<133::AID-NET5>3.0.CO;2-L","volume":"27","author":"G.H. Polychronopoulos","year":"1996","unstructured":"Polychronopoulos, G.H., Tsitsiklis, J.N.: Stochastic shortest path problems with recourse. Networks\u00a027(2), 133\u2013143 (1996)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:35Z","timestamp":1605642035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11841036_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}