{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:16Z","timestamp":1781259376565,"version":"3.54.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T00:00:00Z","timestamp":1479686400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_146660"],"award-info":[{"award-number":["200021_146660"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s10107-016-1089-0","type":"journal-article","created":{"date-parts":[[2016,11,20]],"date-time":"2016-11-20T21:37:20Z","timestamp":1479677840000},"page":"325-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Geometric random edge"],"prefix":"10.1007","volume":"164","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7928-1076","authenticated-orcid":false,"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,11,21]]},"reference":[{"key":"1089_CR1","doi-asserted-by":"crossref","unstructured":"Applegate, D., Kannan, R.: Sampling and integration of near log-concave functions. In: STOC \u201991: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 156\u2013163. ACM, New York (1991)","DOI":"10.1145\/103418.103439"},{"key":"1089_CR2","doi-asserted-by":"crossref","unstructured":"Bobkov, S.G., Houdr\u00e9, C.: Isoperimetric constants for product probability measures. Ann. Probab. 25(1), 184\u2013205 (1997)","DOI":"10.1214\/aop\/1024404284"},{"key":"1089_CR3","doi-asserted-by":"crossref","unstructured":"Bonifas, N., Di Summa, M., Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry, SoCG \u201912, pp. 357\u2013362 (2012)","DOI":"10.1145\/2261250.2261304"},{"key":"1089_CR4","unstructured":"Brunsch, T., Gro\u00dfwendt, A., R\u00f6glin, H.: Solving totally unimodular lps with the shadow vertex algorithm. In: 32nd International Symposium on Theoretical Aspects of Computer Science, p. 171 (2015)"},{"key":"1089_CR5","doi-asserted-by":"crossref","unstructured":"Brunsch, T., R\u00f6glin, H.: Finding short paths on polytopes by the shadow vertex algorithm. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) Automata, Languages, and Programming, pp. 279\u2013290. Springer, Berlin(2013)","DOI":"10.1007\/978-3-642-39206-1_24"},{"key":"1089_CR6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01582230","volume":"34","author":"W Cook","year":"1986","unstructured":"Cook, W., Gerards, A.M.H., Schrijver, A., Tardos, E.: Sensitivity theorems in integer linear programming. Math. Program. 34, 251\u2013264 (1986)","journal-title":"Math. Program."},{"key":"1089_CR7","unstructured":"Dadush, D., H\u00e4hnle, N.: On the shadow simplex method for curved polyhedra. In: 31st International Symposium on Computational Geometry, SoCG 2015, June 22\u201325, 2015, Eindhoven, The Netherlands, pp. 345\u2013359 (2015)"},{"key":"1089_CR8","first-page":"339","volume-title":"Activity Analysis of Production and Allocation","author":"GB Dantzig","year":"1951","unstructured":"Dantzig, G.B.: Maximization of a linear function of variables subject to linear inequalities. In: Koopmans, T.C. (ed.) Activity Analysis of Production and Allocation, pp. 339\u2013347. Wiley, New York (1951)"},{"issue":"1, Ser. A","key":"1089_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582563","volume":"64","author":"M Dyer","year":"1994","unstructured":"Dyer, M., Frieze, A.: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64(1, Ser. A), 1\u201316 (1994)","journal-title":"Math. Program."},{"key":"1089_CR10","doi-asserted-by":"crossref","unstructured":"Friedmann, Oliver.: A subexponential lower bound for Zadeh\u2019s pivoting rule for solving linear programs and games. In: Integer Programming and Combinatoral Optimization, pp. 192\u2013206. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-20807-2_16"},{"key":"1089_CR11","doi-asserted-by":"crossref","unstructured":"Friedmann, O., Hansen, T.D., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC\u201911\u2014Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 283\u2013292. ACM, New York (2011)","DOI":"10.1145\/1993636.1993675"},{"issue":"1","key":"1089_CR12","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/05062370X","volume":"21","author":"B G\u00e4rtner","year":"2007","unstructured":"G\u00e4rtner, B., Kaibel, V.: Two new bounds for the random-edge simplex-algorithm. SIAM J. Discrete Math. 21(1), 178\u2013190 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"1089_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, Volume 2 of Algorithms and Combinatorics","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Volume 2 of Algorithms and Combinatorics. Springer, Berlin (1988)"},{"key":"1089_CR14","doi-asserted-by":"crossref","unstructured":"Hansen, T.D., Paterson, M., Zwick, U.: Improved upper bounds for random-edge and random-jump on abstract cubes. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 874\u2013881. Society for Industrial and Applied Mathematics (2014)","DOI":"10.1137\/1.9781611973402.65"},{"key":"1089_CR15","doi-asserted-by":"crossref","unstructured":"Kalai, Gil.: A subexponential randomized simplex algorithm (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC92), pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"issue":"4","key":"1089_CR16","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"1089_CR17","first-page":"1093","volume":"244","author":"LG Khachiyan","year":"1979","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244, 1093\u20131097 (1979)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"1089_CR18","unstructured":"Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Inequalities, III (Proceedings of Third Symposium, Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pp. 159\u2013175. Academic Press, New York (1972)"},{"issue":"4","key":"1089_CR19","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L., Simonovits, M.: Random walks in a convex body and an improved volume algorithm. Random Struct. Algorithms 4(4), 359\u2013412 (1993)","journal-title":"Random Struct. Algorithms"},{"key":"1089_CR20","first-page":"1","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random walks on graphs. Combinatorics Paul Erdos Eighty 2, 1\u201346 (1993)","journal-title":"Combinatorics Paul Erdos Eighty"},{"issue":"4\u20135","key":"1089_CR21","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4\u20135), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"1089_CR22","first-page":"447","volume-title":"Optimization, Volume 1 of Handbooks in Operations Research and Management Science","author":"GL Nemhauser","year":"1989","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer programming. In: Nemhauser, G.L., et al. (eds.) Optimization, Volume 1 of Handbooks in Operations Research and Management Science, pp. 447\u2013527. Elsevier, Amsterdam (1989)"},{"key":"1089_CR23","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, London (1986)"},{"key":"1089_CR24","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput. 82, 93\u2013133 (1989)","journal-title":"Inf. Comput."},{"issue":"3","key":"1089_CR25","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004). (electronic)","journal-title":"J. ACM"},{"issue":"2","key":"1089_CR26","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9 Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2), 250\u2013256 (1986)","journal-title":"Oper. Res."},{"key":"1089_CR27","first-page":"573","volume":"52","author":"S Vempala","year":"2005","unstructured":"Vempala, S.: Geometric random walks: a survey. MSRI Comb. Comput. Geom. 52, 573\u2013612 (2005)","journal-title":"MSRI Comb. Comput. Geom."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1089-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1089-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1089-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T16:03:50Z","timestamp":1568563430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1089-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,21]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["1089"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1089-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,21]]}}}