Random sampling in cut, flow, and network design problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random sampling in cut, flow, and network design problems

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 648 - 657

Year of Publication: 1994

ISBN:0-89791-663-8

Author

David R. Karger

Department of Computer Science, Stanford University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 99, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195422 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	H. Chernoff. "A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations". Annals of Mathematical Statistics, 23:493-509# 1952.
	2	E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. "On the structure of a family of minimal weighted cuts in a graph". In A. A. Fridman, editor, .Studies in Discrete Optimization, pages 290-306. Nauka Publ., 1976.
	3	J. Edmonds. "Minimum partition of a matroid into independents subsets". Journal of Research of the National Bureau of Standards, 69:67-72, 1965.
	4	D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. "Sparsificationma technique for speeding up dynamic graph algorithms". In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 60-69, Oct. 1992.
	5	K. P. Eswaran and R. E. Tarjan. "Augmentation problems". SIAM Journal on Computing, 5:653-665# 1976.
	6	L. R. Ford, jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.
	7	Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
	8	Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
	9	H. N. Gabow. "A framework for cost-scaling algorithms for submodular flow problems". In Proceedings of the 34#h Annual Symposium on Foundations of Computer Science, pages 449-458, Nov. 1993.
	10	H. N. Gabow, M. X. Goemans, and D. P. Williamson. "An efficient approximation algorithm for the survivable network design problem", in Proceedings of the Third MPS Conference on Integer Programming and Combinatorial Optimization# pages 57-74, 1993.
	11	M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
	12	R. E. Gomory and T. C. Hu. "Multi-terminal network flows". Journal of the Society of Industrial and Applied Mathematics, 9(4):551-570, Dec. 1961.
	13	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	14	D. R. Karger. "Random sampling in matroids, with applications to graph connectivity and minimum spanning trees". In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993.
	15	David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
	16	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167281]
	17	Samir Khuller , Baruch Schieber, Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs, SIAM Journal on Computing, v.20 n.2, p.352-375, April 1990 [doi>10.1137/0220022]
	18	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.759-770, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129786]
	19	P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
	20	Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.9-15, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195084]
	21	T. Leighton and S. Rao. "An approximate maxflow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms". In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422-4;31. IEEE, Oct. 1988.
	22	David W. Matula, A linear time 2 + &&egr; approximation algorithm for edge connectivity, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.500-504, January 25-27, 1993, Austin, Texas, United States
	23	Hiroshi Nagamochi , Toshihide Ibaraki, On max-flow min-cut and integral flow properties for multicommodity flows in directed networks, Information Processing Letters, v.31 n.6, p.279-285, June 19, 1989 [doi>10.1016/0020-0190(89)90087-2]
	24	Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
	25	H. Nagamochi and T. Ibaraki. "Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica, 7:583-596, 1992.
	26	C. S. J. A. Nash-Williams. "Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings/'. In W. T. Tutte, editor, Recent Progress in Combinatorics, pages 133-149. Academic Press, 1969.
	27	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	28	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	29	David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani, A primal-dual approximation algorithm for generalized Steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.708-717, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167268]

CITED BY 13

	David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Cristina G. Fernandes, A better approximation ratio for the minimum k-edge-connected spanning subgraph problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.629-638, January 05-07, 1997, New Orleans, Louisiana, United States
	Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.1-10, May 29-June 01, 1995, Las Vegas, Nevada, United States
	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	David R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.11-17, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States
	Mikkel Thorup, Decremental dynamic connectivity, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.305-313, January 05-07, 1997, New Orleans, Louisiana, United States
	David R. Karger, Using random sampling to find maximum flows in uncapacitated undirected graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.240-249, May 04-06, 1997, El Paso, Texas, United States
	Pavlos S. Efraimidis , Paul G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters, v.97 n.5, p.181-185, 16 March 2006
	David R. Karger , Ray P. Tai, Implementing a fully polynomial time approximation scheme for all terminal network reliability, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.334-343, January 05-07, 1997, New Orleans, Louisiana, United States
	David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996
	Ramesh Hariharan , Telikepalli Kavitha , Debmalya Panigrahi, Efficient algorithms for computing all low s-t edge connectivities and related problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.127-136, January 07-09, 2007, New Orleans, Louisiana
	Ashish Goel , Michael Kapralov , Sanjeev Khanna, Perfect matchings via uniform sampling in regular bipartite graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.11-17, January 04-06, 2009, New York, New York