{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:04:05Z","timestamp":1773230645695,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1994,3]]},"DOI":"10.1007\/bf01582563","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:39:29Z","timestamp":1114677569000},"page":"1-16","source":"Crossref","is-referenced-by-count":41,"title":["Random walks, totally unimodular matrices, and a randomised dual simplex algorithm"],"prefix":"10.1007","volume":"64","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","first-page":"243","volume-title":"S\u00e9minaire de Probabilit\u00e9s XVIII, 1981\u201382, Springer Lecture Note in Mathematics No. 986","author":"D. Aldous","year":"1982","unstructured":"D. Aldous, \u201cRandom walks on finite groups and rapidly mixing Markov chains,\u201dS\u00e9minaire de Probabilit\u00e9s XVIII, 1981\u201382, Springer Lecture Note in Mathematics No. 986 (Springer, Berlin, 1982) pp. 243\u2013297."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/0403039","volume":"3","author":"D. Aldous","year":"1990","unstructured":"D. Aldous, \u201cThe random walk construction of uniform spanning trees and uniform labelled trees,\u201dSIAM Journal on Discrete Mathematics 3 (1990) 450\u2013465.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"CR3","unstructured":"D. Applegate and R. Kannan, \u201cSampling and integration of near logconcave functions,\u201dProceedings of the 23rd ACM Symposium on Theory of Computing (1991) pp. 156\u2013163."},{"key":"CR4","volume-title":"Algebra","author":"J.W. Archbold","year":"1958","unstructured":"J.W. Archbold,Algebra (Pitman, London, 1958)."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"A.Z. Broder, \u201cHow hard is it to marry at random? (On the approximation of the permanent),\u201dProceedings of the 18th ACM Symposium on Theory of Computing (1986) pp. 50\u201358.","DOI":"10.1145\/12130.12136"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"A.Z. Broder, \u201cGenerating random spanning trees,\u201dProceedings of the 30th Annual Symposium on Foundations of Computer Science (1989) pp. 442\u2013447.","DOI":"10.1109\/SFCS.1989.63516"},{"key":"CR7","volume-title":"Geometric Inequalities","author":"Y.D. Burago","year":"1980","unstructured":"Y.D. Burago and V.A. Zalgaller,Geometric Inequalities (Springer, Berlin, 1980)."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"W.H. Cunningham, \u201cTheoretical properties of the network simplex method,\u201dMathematics of Operations Research 4, 196\u2013208.","DOI":"10.1287\/moor.4.2.196"},{"key":"CR9","unstructured":"M.E. Dyer, \u201cApproximation of mixed volumes,\u201d in preparation."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"M.E. Dyer and A.M. Frieze, \u201cComputing the volume of convex bodies: a case where randomness probably helps,\u201d to appear in: B. Bollob\u00e1s, ed.,Proceedings of AMS Short Course on Probability and Combinatorics.","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M.E. Dyer","year":"1991","unstructured":"M.E. Dyer, A.M. Frieze and R. Kannan, \u201cA random polynomial time algorithm for approximating the volume of convex bodies,\u201dJournal of the ACM 38 (1991), 1\u201317.","journal-title":"Journal of the ACM"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Mihail, \u201cBalanced matroids,\u201dProceedings of the 24th Annual ACM Symposium on Theory of Computing (1992) pp. 26\u201338.","DOI":"10.1145\/129712.129716"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M.R. Jerrum","year":"1989","unstructured":"M.R. Jerrum and A.J. Sinclair, \u201cApproximating the permanent,\u201dSIAM Journal on Computing 18 (1989) 1149\u20131178.","journal-title":"SIAM Journal on Computing"},{"key":"CR14","volume-title":"Polynomial-time approximation algorithms for the Ising model","author":"M.R. Jerrum","year":"1989","unstructured":"M.R. Jerrum and A.J. Sinclair, \u201cPolynomial-time approximation algorithms for the Ising model,\u201d Department of Computer Science, Edinburgh University (Edinburgh, 1989)."},{"key":"CR15","unstructured":"G. Kalai, \u201cThe diameter of graphs of convex polytopes andf-vector theory,\u201d to appear in:DIMACS Series in Discrete Mathematics and Theoretical Computer Science."},{"key":"CR16","volume-title":"\u201cOn the conductance of order Markov chains,\u201d Technical Report DCS TR 268","author":"A. Karzanov","year":"1990","unstructured":"A. Karzanov and L.G. Khachyan, \u201cOn the conductance of order Markov chains,\u201d Technical Report DCS TR 268, Rutgers University (New Brunswick, NJ, 1990)."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and M. Simonovits, \u201cThe mixing rate of Markov chains, an isoperimetric inequality and computing the volume,\u201dProceedings of the 31st Annual Symposium on Foundations of Computer Science (1990) pp. 364\u2013355.","DOI":"10.1109\/FSCS.1990.89553"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller and E. Teller, Equation of state calculation by fast computing machines,Journal of Chemical Physics 21 (1953) 1087\u20131091.","journal-title":"Journal of Chemical Physics"},{"key":"CR19","unstructured":"M. Mihail and P. Winkler, \u201cOn the number of Euler orientations of a graph,\u2019Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (1992) pp. 138\u2013145."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D. Naddef","year":"1989","unstructured":"D. Naddef, \u201cThe Hirsch conjecture is true for 0\u20131 polytopes,\u201dMathematical Programming 45 (1989) 109\u2013110.","journal-title":"Mathematical Programming"},{"key":"CR21","volume-title":"The Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver,The Theory of Linear and Integer Programming (Wiley, Chichester, 1986)."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A.J. Sinclair","year":"1989","unstructured":"A.J. Sinclair and M.R. Jerrum, \u201cApproximate counting, uniform generation and rapidly mixing Markov chains,\u201dInformation and Computation 82 (1989) 93\u2013133.","journal-title":"Information and Computation"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0097-3165(81)90053-4","volume":"31","author":"R.M. Stanley","year":"1981","unstructured":"R.M. Stanley, \u201cTwo combinatorial applications of the Aleksandrov-Fenchel inequalities,\u201dJournal of Combinatorial Theory A 31 (1981) 56\u201365.","journal-title":"Journal of Combinatorial Theory A"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"E. Tardos, \u201cA strongly polynomial algorithm to solve combinatorial linear programs,\u201dOperations Research 34 (1986) 250\u2013256.","journal-title":"Operations Research"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1287\/moor.16.2.272","volume":"16","author":"R.E. Tarjan","year":"1991","unstructured":"R.E. Tarjan, \u201cEfficiency of the primal network simplex method algorithm for the minimum-cost circulation problem,\u201dMathematics of Operations Research 16 (1991), 272\u2013291.","journal-title":"Mathematics of Operations Research"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01580132","volume":"5","author":"N. Zadeh","year":"1973","unstructured":"N. Zadeh, \u201cA bad network for the simplex method and other minimum cost flow algorithms,\u201dMathematical Programming 5 (1973) 255\u2013266.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582563.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01582563\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:15:50Z","timestamp":1556896550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01582563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":26,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["BF01582563"],"URL":"https:\/\/doi.org\/10.1007\/bf01582563","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}