{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:05:31Z","timestamp":1758265531864},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"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":[[1998,6]]},"DOI":"10.1007\/bf01585865","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:50Z","timestamp":1114677770000},"page":"41-81","source":"Crossref","is-referenced-by-count":12,"title":["Random sampling and greedy sparsification for matroid optimization problems"],"prefix":"10.1007","volume":"82","author":[{"given":"David R.","family":"Karger","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0167-6377(92)90045-5","volume":"12","author":"F. Barahona","year":"1992","unstructured":"F. Barahona, Separating from the dominant of the spanning tree polytope, Operations Research Letters 12 (1992) 201\u2013203.","journal-title":"Operations Research Letters"},{"issue":"1","key":"CR2","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/moor.20.1.104","volume":"20","author":"F. Barahona","year":"1995","unstructured":"F. Barahona, Packing spanning trees, Mathematics of Operation Research 20 (1) (1995) 104\u2013115.","journal-title":"Mathematics of Operation Research"},{"key":"CR3","first-page":"47","volume-title":"Approximates\u2014t min-cuts in \u00d5(n 2) time, Proceedings of the 28th ACM Symposium on Theory of Computing","author":"A.A. Bencz\u00far","year":"1996","unstructured":"A.A. Bencz\u00far, D.R. Karger, Approximates\u2014t min-cuts in \u00d5(n 2) time, Proceedings of the 28th ACM Symposium on Theory of Computing, ACM, New York, 1996, pp. 47\u201355."},{"key":"CR4","volume-title":"Random Graphs, Harcourt","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs, Harcourt. Brace and Janovich, New York, 1985."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics 23 (1952) 493\u2013509.","journal-title":"Annals of Mathematical Statistics"},{"key":"CR6","volume-title":"The Combinatorics of Network Reliability, The International Series of Monographs on Computer Science, vol. 4","author":"C.J. Colbourn","year":"1987","unstructured":"C.J. Colbourn, The Combinatorics of Network Reliability, The International Series of Monographs on Computer Science, vol. 4, Oxford University Press, Oxford, 1987."},{"key":"CR7","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"issue":"6","key":"CR8","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"B. Dixon, M. Rauch, R.E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing 21 (6) (1992) 1184\u20131192.","journal-title":"SIAM Journal on Computing"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.6028\/jres.069B.004","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Minimum partition of a matroid into independents subsets, Journal of Research of the National Bureau of Standards 69 (1965) 67\u201372.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"J. Edmonds, Matroids and the greedy algorithm, Mathematical Programming 1 (1971) 126\u2013136.","journal-title":"Mathematical Programming"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"P. Erd\u00f6s, A. R\u00e9nyi, On random graphs I, Publicacions Matematiques Debrecen 6 (1959) 290\u2013297.","journal-title":"Publicacions Matematiques Debrecen"},{"key":"CR12","first-page":"26","volume-title":"Balanced matroids, Proceedings of the 24th ACM Symposium on Theory of Computing","author":"T. Feder","year":"1992","unstructured":"T. Feder, M. Mihail, Balanced matroids, Proceedings of the 24th ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 26\u201338."},{"key":"CR13","volume-title":"An Introduction to Probability Theory and its Applications, vol. 1","author":"W. Feller","year":"1968","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications, vol. 1, 3rd ed., Wiley, New York, 1968.","edition":"3rd ed."},{"issue":"3","key":"CR14","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"R.W. Floyd","year":"1975","unstructured":"R.W. Floyd, R.L. Rivest, Expected time bounds for selection, Communications of the ACM 18 (3) (1975) 165\u2013172.","journal-title":"Communications of the ACM"},{"issue":"2","key":"CR15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"H.N. Gabow","year":"1995","unstructured":"H.N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Journal of Computer and System Sciences 50 (2) (1995) 259\u2013273.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"CR16","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01758774","volume":"7","author":"H.N. Gabow","year":"1992","unstructured":"H.N. Gabow, H.H. Westermann, Forests, frames, and games: Algorithms for matroid sums and applications, Algorithmica 7 (5) (1992) 465\u2013497.","journal-title":"Algorithmica"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(83)90031-5","volume":"16","author":"D. Gusfield","year":"1983","unstructured":"D. Gusfield, Connectivity and edge disjoint spanning trees, Information Processing Letters 16 (1983) 87\u201389.","journal-title":"Information Processing Letters"},{"key":"CR18","first-page":"43","volume":"79","author":"A. Itai","year":"1988","unstructured":"A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Control 79 (1988) 43\u201359.","journal-title":"Information and Control"},{"key":"CR19","unstructured":"D.R. Karger, Approximating, verifying, and constructing minimum spanning forests, Manuscript, 1992."},{"key":"CR20","first-page":"84","volume-title":"Random sampling in matroids, with applications to graph connectivity and minimum spanning trees, Proceedings of the 34th Annual Symposium on the Foundations of Computer Science","author":"D.R. Karger","year":"1993","unstructured":"D.R. Karger, Random sampling in matroids, with applications to graph connectivity and minimum spanning trees, Proceedings of the 34th Annual Symposium on the Foundations of Computer Science, IEEE Computer Soc. Press, Silver Spring, MD, 1993, pp. 84\u201393 (submitted for publication)."},{"key":"CR21","first-page":"648","volume-title":"Random sampling in cut, flow, and network design problems, Proceedings of the 26th ACM Symposium on Theory of Computing","author":"D.R. Karger","year":"1994","unstructured":"D.R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the 26th ACM Symposium on Theory of Computing, ACM, New York, 1994, pp. 648\u2013657. To appear in Mathematics of Operations Research."},{"key":"CR22","first-page":"56","volume-title":"Minimum cuts in near-linear time, Proceedings of the 28th ACM Symposium on Theory of Computing","author":"D.R. Karger","year":"1996","unstructured":"D.R. Karger, Minimum cuts in near-linear time, Proceedings of the 28th ACM Symposium on Theory of Computing, ACM, New York, 1996, pp. 56\u201363."},{"key":"CR23","first-page":"240","volume-title":"Using random sampling to find flows in uncapacitated undirected graphs, Proceedings of the 29th ACM Symposium on Theory of Computing","author":"D.R. Karger","year":"1997","unstructured":"D.R. Karger, Using random sampling to find flows in uncapacitated undirected graphs, Proceedings of the 29th ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 240\u2013249."},{"issue":"2","key":"CR24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"D.R. Karger, P.N. Klein, R.E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM 42 (2) (1995) 321\u2013328.","journal-title":"Journal of the ACM"},{"issue":"4","key":"CR25","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"D.R. Karger, C. Stein, A new approach to the minimum cut problem, Journal of the ACM 43 (4) (1996) 601\u2013640 (preliminary portions appeared in SODA 1992 and STOC 1993).","journal-title":"Journal of the ACM"},{"key":"CR26","first-page":"190","volume-title":"Probabilistic recurrence relations, Proceedings of the 23rd ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1991","unstructured":"R.M. Karp, Probabilistic recurrence relations, Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 190\u2013197."},{"key":"CR27","first-page":"9","volume-title":"A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the 26th ACM Symposium on Theory of Computing","author":"P.N. Klein","year":"1994","unstructured":"P.N. Klein, R.E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the 26th ACM Symposium on Theory of Computing, ACM, New York, 1994, pp. 9\u201315."},{"key":"CR28","unstructured":"D.E. Knuth, Matroid partitioning, Technical Report STAN-CS-73-342, Stanford University, 1973."},{"key":"CR29","first-page":"357","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"D.E. Knuth","year":"1976","unstructured":"D.E. Knuth, A.C. Yao, The complexity of nonuniform random number generation, in: J.F. Traub (Ed.), Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 1976, pp. 357\u2013428."},{"issue":"1","key":"CR30","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal Jr.","year":"1956","unstructured":"J.B. Kruskal Jr., On the shortest spanning subtree of a graph and the travelling salesman problem, Proceedings of the American Mathematical Society 7 (1) (1956) 48\u201350.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"CR31","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, New York, 1976."},{"issue":"1","key":"CR32","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1287\/ijoc.4.1.70","volume":"4","author":"J. Lee","year":"1992","unstructured":"J. Lee, J. Ryan, Matroid applications and algorithms, ORSA Journal on Computing 4 (1) (1992) 70\u201396.","journal-title":"ORSA Journal on Computing"},{"key":"CR33","first-page":"249","volume-title":"Determining edge connectivity in O(nm), Proceedings of the 28th Annual Symposium on the Foundations of Computer Science","author":"D.W. Matula","year":"1987","unstructured":"D.W. Matula, Determining edge connectivity in O(nm), Proceedings of the 28th Annual Symposium on the Foundations of Computer Science, IEEE Computer Soc. Press, Silver Spring, MD, 1987, pp. 249\u2013251."},{"key":"CR34","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995."},{"key":"CR35","volume-title":"Computational Geometry","author":"K. Mulmuley","year":"1994","unstructured":"K. Mulmuley, Computational Geometry, Prentice-Hall, Englewood Cliffs, NJ, 1994."},{"issue":"1","key":"CR36","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi, T. Ibaraki, Computing edge connectivity in multigraphs and capacitated graphs, SIAM Journal of Discrete Mathematics 5 (1) (1992) 54\u201366.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"CR37","first-page":"445","volume":"36","author":"C. St","year":"1961","unstructured":"C. St, J.A. Nash-Wiliams, Edge disjoint spanning trees of finite graphs, Journal of the London Mathematical Society 36 (1961) 445\u2013450.","journal-title":"Journal of the London Mathematical Society"},{"key":"CR38","first-page":"86","volume":"27","author":"V.P. Polesskii","year":"1990","unstructured":"V.P. Polesskii, Bounds on the connectedness probability of a random graph, Problems of Information Transmition 27 (1990) 86\u201397.","journal-title":"Problems of Information Transmition"},{"key":"CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-22143-3","volume-title":"Matroid Theory and its Applications In Electric Network Theory and in Statics, Number 6 in Algorithms and Combinatorics","author":"A. Recski","year":"1989","unstructured":"A. Recski, Matroid Theory and its Applications In Electric Network Theory and in Statics, Number 6 in Algorithms and Combinatorics, Springer, Berlin, 1989."},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"J.H. Reif, P. Spirakis, Random matroids, Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 385\u2013397.","DOI":"10.1145\/800141.804688"},{"key":"CR41","unstructured":"A. Schrijver (Ed.), Packing and covering in combinatorics, Number 106 in Mathematical Centre Tracts, Mathematical Centre, 1979."},{"key":"CR42","volume-title":"Moderne Algebra","author":"B.L. Waerden Van Der","year":"1937","unstructured":"B.L. Van Der Waerden, Moderne Algebra, Springer, Berlin, 1937."},{"key":"CR43","volume-title":"Matroid Theory, London Mathematical Society Monographs","author":"D.J.A. Welsh","year":"1976","unstructured":"D.J.A. Welsh, Matroid Theory, London Mathematical Society Monographs, Academic Press, New York, 1976."},{"key":"CR44","doi-asserted-by":"crossref","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"H. Whitney, On the abstract properties of linear independence, American Journal of Mathematics 57 (1935) 509\u2013533.","journal-title":"American Journal of Mathematics"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585865.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585865\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T02:33:56Z","timestamp":1683081236000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["BF01585865"],"URL":"https:\/\/doi.org\/10.1007\/bf01585865","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}