Random Sampling in Cut, Flow, and Network Design Problems

References

• Aggarwal A. Proc. 25th ACM Sympos. Theory Comput. (1993) (ACM Press) Google Scholar
• Aggarwal A. , Garg N. A scaling technique for better network design. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994) 233 240 Google Scholar
• Agrawal A. , Klein P. , Ravi R. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. (1995) 24 3 440 456 Crossref, Google Scholar
• Ahuja R. K. , Magnanti T. L. , Orlin J. B. Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, New Jersey) Google Scholar
• Aumann Y. , Rabani Y. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. (1998) 27 1 291 301 Crossref, Google Scholar
• Benczúr A. A. , Karger D. R. Approximate s−t min-cuts in Õ(n 2) time. Proc. 28th ACM Sympos. Theory Comput. (1996) (ACM Press) 47 55 Google Scholar
• Chernoff H. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. (1952) 23 493 509 Crossref, Google Scholar
• Clarkson K. L. New applications of random sampling in computational geometry. Discrete Comput. Geom. (1987) 2 195 222 Crossref, Google Scholar
• Clarkson K. L. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM (1995) 42 2 488 499 Crossref, Google Scholar
• Clarkson K. L. , Shor P. W. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. (1987) 4 5 387 421 Crossref, Google Scholar
• Dinitz E. A. , Karzanov A. V. , Lomonosov M. V. , Fridman A. A. On the structure of a family of minimum weighted cuts in a graph. Studies in Discrete Optimization (1976) (Nauka Publishers) 290 306 Google Scholar
• Edmonds J. Minimum partition of a matroid into independents subsets. J. Res. Nat. Bur. Standards (1965) 69 67 72 Crossref, Google Scholar
• Eppstein D. , Galil Z. , Italiano G. F. , Nissenzweig A. Sparsification—A technique for speeding up dynamic graph algorithms. Proc. 33rd Annual Sympos. Foundations Comput. Sci. (1992) IEEE Computer Society Press 60 69 Crossref, Google Scholar
• Erdös P. , Rényi A. On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. (1961) 12 261 267 Crossref, Google Scholar
• Eswaran K. P. , Tarjan R. E. Augmentation problems. SIAM J. Comput. (1976) 5 653 665 Crossref, Google Scholar
• Feller W. An Introduction to Probability Theory and Its Applications (1968) 1 3rd ed. (John Wiley and Sons, New York) Google Scholar
• Floyd R. W. , Rivest R. L. Expected time bounds for selection. Comm. ACM 18 3 165 172 Crossref, Google Scholar
• Ford L. R. , Fulkerson D. R. Flows in Networks (1962) (Princeton University Press, Princeton, New Jersey) Crossref, Google Scholar
• Frank A. , Korte B. , Lovász L. , Prömel H. J. , Schrijver A. Packing paths, circuits, and cuts—A survey. Paths, Flows, and VLSI Layout (1990) 9 (Springer-Verlag, Heidelberg) . Algorithms and Combinatorics Chapter 4 Google Scholar
• Gabber O. , Galil Z. Explicit construction of linear-sized superconcentrators. J. Comput. System Sci. (1981) 22 407 420 Crossref, Google Scholar
• Gabow H. N. Applications of a poset representation to edge connectivity and graph rigidity. Proc. 32nd Annual Sympos. Foundations Comput. Sci. (1991) IEEE: IEEE Computer Society Press 812 821 Crossref, Google Scholar
• Gabow H. N. A framework for cost-scaling algorithms for submodular flow problems. Proc. 34th Annual Sympos. Foundations Comput. Sci. (1993) IEEE Computer Society Press 449 458 Crossref, Google Scholar
• Gabow H. N. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. System Sci. (1995) 50 2 259 273 Crossref, Google Scholar
• Gabow H. N. , Goemans M. X. , Williamson D. P. An efficient approximation algorithm for the survivable network design problem. Proc. Third MPS Conf. Integer Programming Combin. Optim. (1993) 57 74 Google Scholar
• Goemans M. X. , Bertsimas D. J. Survivable networks, linear programming relaxations and the parsimonious property. Math. Programming (1993) 60 145 166 Crossref, Google Scholar
• Goemans M. X. , Goldberg A. , Plotkin S. , Shmoys D. , Tardos É. , Williamson D. Improved approximation algorithms for network design problems. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994) (ACM-SIAM) 223 232 Google Scholar
• Grötschel M. , Lovász L. , Schrijver A. Geometric Algorithms and Combinatorial Optimization (1988) 2 (Springer-Verlag, Berlin, Germany) . Algorithms and Combinatorics Crossref, Google Scholar
• Guibas L. Proc. 34th Annual Sympos. Foundations Comput. Sci. (1993) IEEE Computer Society Press Google Scholar
• Karger D. R. Random sampling in cut, flow, and network design problems. Proc. 26th ACM Sympos. Theory Comput. (1994a) ACM Press 648 657 Crossref, Google Scholar
• Karger D. R. Random Sampling in Graph Optimization Problems (1994b) . Ph.D. thesis, Stanford University, Stanford, CA 94305. Contact at [email protected] Available from http://theory.lcs.mit.edu/~karger karger Google Scholar
• Karger D. R. Using randomized sparsification to approximate minimum cuts. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994c) January 424 432 Google Scholar
• Karger D. R. Minimum cuts in near-linear time. Proc. 28th ACM Sympos. Theory of Comput. (1996) ACM Press May 56 63 Crossref, Google Scholar
• Karger D. R. , Karloff H. Better random sampling algorithms for flows in undirected graphs. Proc. 9th Annual ACM-SIAM Sympos. Discrete Algorithms (1998a) January 490 499 Google Scholar
• Karger D. R. Random sampling and greedy sparsification in matroid optimization problems. Math. Programming B (1998b) 82 1–2(June) 41 81 Crossref, Google Scholar
• Karger D. R. , Klein P. N. , Tarjan R. E. A randomized linear-time algorithm to find minimum spanning trees. J. ACM (1995) 42 2 321 328 Crossref, Google Scholar
• Karger D. R. , Levine M. Finding maximum flows in simple undirected graphs seems faster than bipartite matching. Proc. 29th ACM Sympos. Theory Comput. (1998) ACM Press May 69 78 Google Scholar
• Karger D. R. , Stein C. An Õ(n 2) algorithm for minimum cuts. Proc. 25th ACM Sympos. Theory Comput. (1993) ACM Press May 757 765 Google Scholar
• Karger D. R. , Stein C. A new approach to the minimum cut problem. J. ACM (1996) 43 4 (July) 601 640 Crossref, Google Scholar
• Khuller S. , Raghavachari B. Improved approximation algorithms for uniform connectivity problems. Proc. 27th ACM Sympos. Theory Comput. (1995) May (ACM Press) 1 10 Crossref, Google Scholar
• Khuller S. , Schieber B. Efficient parallel algorithms for testing connectivity and finding disjoint s−t paths in graphs. SIAM J. Comput. (1991) 20 2 (April) 352 375 Crossref, Google Scholar
• Khuller S. , Vishkin U. Biconnectivity approximations and graph carvings. J. ACM (1994) 41 2 (March) 214 235 Crossref, Google Scholar
• Klein P. , Plotkin S. A. , Stein C. , Tardos É. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput. (1994) 23 3 466 487 Crossref, Google Scholar
• Knuth D. E. Fundamental Algorithms (1973) 1 2nd ed. (Addison-Wesley Publishing Company, Reading, MA) . of The Art of Computer Programming Google Scholar
• Knuth D. E. , Yao A. C. , Traub J. F. The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results (1976) (Academic Press, New York) 357 428 Google Scholar
• Leighton T. , Rao S. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Proc. 29th Annual Sympos. Foundations Comput. Sci. (1988) October (IEEE Computer Society Press) 422 431 Crossref, Google Scholar
• Linial N. , London E. , Rabinovich Y. The geometry of graphs and some of its algorithmic applications. Combinatorica (1995) 15 2 215 246 Crossref, Google Scholar
• Lomonosov M. V. , Polesskii V. P. Lower bound of network reliability. Problems of Inform. Transmission (1971) 7 118 123 Google Scholar
• Matula D. W. A linear time 2 + ɛ approximation algorithm for edge connectivity. Proc. 4th Annual ACM-SIAM Sympos. Discrete Algorithms (1993) January (ACM-SIAM) 500 504 Google Scholar
• Miller G. Proc. 28th ACM Sympos. Theory Comput. (1996) May (ACM Press) Google Scholar
• Miller G. , Raghavan P. Randomized Algorithms (1995) (Cambridge University Press, New York) Google Scholar
• Nagamochi H. , Ibaraki T. Computing edge connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. (1992a) 5 1 (February) 54 66 Crossref, Google Scholar
• Nagamochi H. , Ibaraki T. Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica (1992b) 7 583 596 Crossref, Google Scholar
• Nash-Williams C. S. J. A. , Tutte W. T. Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings. Recent Progress in Combinatorics (1969) (Academic Press, New York) 133 149 Google Scholar
• Raghavan P. Probabilistic construction of deterministic algorithms: Approximate packing integer programs. J. Comput. System Sci. (1988) 37 2 (October) 130 43 Crossref, Google Scholar
• Raghavan P. , Thompson C. D. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica (1987) 7 4 365 374 Crossref, Google Scholar
• Sleator D. D. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994) January (ACM-SIAM) Google Scholar
• Tarjan R. E. Data Structures and Network Algorithms (1983) 44 . of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM Google Scholar
• Williamson D. , Goemans M. X. , Mihail M. , Vazirani V. V. A primal-dual approximation algorithm for generalized Steiner problems. ACM Sympos. Theory Comput. (1993) (ACM Press) 708 717 Crossref, Google Scholar
• Winter P. Generalized Steiner problem in outerplanar networks. Networks (1987) 17 129 167 Crossref, Google Scholar