Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Full text

Pdf (980 KB)

Source

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

Atlanta, Georgia, United States

Pages: 19 - 28

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Venkatesan Guruswami	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA
Sanjeev Khanna	Bell Labs, 700 Mountain Avenue, Murray Hill, NJ
Rajmohan Rajaraman	College of Computer Science, Northeastern University, Boston, MA
Bruce Shepherd	Bell Labs, 700 Mountain Avenue, Murray Hill, NJ
Mihalis Yannakakis	Bell Labs, 700 Mountain Avenue, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 48, Citation Count: 29

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/301250.301262 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	A. BAVEJA AND A. $RINIVASAN. Approximation algorithms for disjoint paths and related routing and packing problems. Submitted, January 1998.
	2	A. BLEY. On the complexity of vertex-disjoint lengthrestricted path problems. Konrad. Zuse-Zentrum fiir In- ~ormationstechnik Berlin Tech. Report $C-98-~0, 1998.
	3	~I. CHERNOFF. A measure of asymptotic e~ciency for tests of a hypothesis based on the sum of observations. Annals o)~ Mathematical Statistics, 23:493-507, 1952.
	4	E. A. DINITZ. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl., Vol. 11 (1970), pp. 1277-1280.
	5	Yefim Dinitz , Naveen Garg , Michel Goemans, On the Single-Source Unsplittable Flow Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.290, November 08-11, 1998
	6	S. EVEN, A. ITA~ AND A. SHAMIR. On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, Vol. 5, No. 4 (I976), pp. 691- 703.
	7	S. FORTUSE, J. HorcRorT ~D J. WYLbm. The directed subgraph homeomorphism problem. Theoretical Computer Science, Vol. 10, No. 2 (1980), pp. 111-121.
	8	N. (~ARG, V. VAZIRANI AND M. YANNAKAKIS. Primaldual approximation algorithms for integral flow and multicut in trees. Algorighmica, 18 (1997), pp. 3-20.
	9	W. HOEFFDING. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
	10	J. H~STAD. Clique is hard to approximate within ~-'. ECCC Technical Report TR97-038. (PreIiminary version in Proc. of FOCS '96, pp. 527-536).
	11	T. C. Hu. Multi-commodity Network Flows. Operations Research, 11(1963), pp. 344-360.
	12	Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
	13	R. M. K~.r.l~. Reducibility among combinatdriat problems. Complexity of Computer Computations, R.E. Miller, J.W. Thatcher, Eds., New York: Plenum Press, 1972, pp. 85-103.
	14	J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
	15	Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
	16	Jon M. Kleinberg, Decision algorithms for unsplittable flow and the half-disjoint paths problem, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.530-539, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276867]
	17	S. G. Ko~r~orouLos. Exact and approximation algorithms for network flow and disjoint-path problems. PhD Thesis, Dartmouth ColIege, Hanover, NH, August 1998.
	18	Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
	19	S. G. KOLL~OrOVLOS ^ND C. STrIN. Approximating disjoint-path problems using greedy algorithms and Packing Integer Programs. IPCO 98.
	20	F. T. LS~C.I~TOl~ ^~) S. B. R~.o. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Proc. oj~ FOCS '88, pp. 422-431.
	21	Bin Ma , Lusheng Wang, On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints, Journal of Computer and System Sciences, v.60 n.1, p.1-12, Feb. 2000 [doi>10.1006/jcss.1999.1661]
	22	W. S. M~.ssrY. Algebraic Topology: An Introduction. Graduate texts in mathematics 56, Springer-Verlag, 1967.
	23	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	24	N. ROBERT$ON AND P. D. SEYMOUR. Outline of a disjoint paths algorithm. In B. Korte, L. Lovksz, H. J. PrSmel, and A. Schrijver, Eds., Paths, Flows and VLSI-Layout. Springer-Verlag, Berlin, 1990.
	25	A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.416, October 19-22, 1997

CITED BY 29

	Amitabha Bagchi , Amitabh Chaudhary , Christian Scheideler , Petr Kolman, Algorithms for fault-tolerant routing in circuit switched networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Micah Adler , Sanjeev Khanna , Rajmohan Rajaraman , Adi Rosén, Time-constrained scheduling of weighted packets on trees and meshes, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 27-30, 1999, Saint Malo, France
	Chandra Chekuri , Sanjeev Khanna, Edge disjoint paths revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Journal of Computer and System Sciences, v.64 n.4, p.820-842, June 2002
	Anindya Basu , Alvin Lin , Sharad Ramanathan, Routing using potentials: a dynamic traffic-aware routing algorithm, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
	Petr Kolman, A note on the greedy algorithm for the unsplittable flow problem, Information Processing Letters, v.88 n.3, p.101-105, 15 November 2003
	R. Sai Anand , Thomas Erlebach , Alexander Hall , Stamatis Stefanakos, Call control with k rejections, Journal of Computer and System Sciences, v.67 n.4, p.707-722, December 2003
	Kasturi Varadarajan , Ganesh Venkataraman, Graph decomposition and a greedy algorithm for edge-disjoint paths, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length menger's theorem and reliable optical routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.504-513, May 21-23, 2000, Portland, Oregon, United States
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
	Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Andreas Bley, On the complexity of vertex-disjoint length-restricted path problems, Computational Complexity, v.12 n.3-4, p.131-149, September 2004
	Thomas Erlebach , Klaus Jansen, Conversion of coloring algorithms into maximum weight independent set algorithms, Discrete Applied Mathematics, v.148 n.1, p.107-125, 30 April 2005
	Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Thomas Erlebach , Danica Vukadinović, Path problems in generalized stars, complete graphs, and brick wall graphs, Discrete Applied Mathematics, v.154 n.4, p.673-683, 15 March 2006
	Thomas Erlebach , Klaus Jansen, Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees, Journal of Experimental Algorithmics (JEA), 7, p.6, 2002
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Petr Kolman , Christian Scheideler, Simple on-line algorithms for the maximum disjoint paths problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.38-47, July 2001, Crete Island, Greece
	Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length Menger's theorem and reliable optical routing, Theoretical Computer Science, v.339 n.2, p.315-332, 12 June 2005
	Matthew Andrews , Lisa Zhang, Logarithmic hardness of the directed congestion minimization problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Nikhil Bansal , Amit Chakrabarti , Amir Epstein , Baruch Schieber, A quasi-PTAS for unsplittable flow on line graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Journal of Algorithms, v.61 n.1, p.20-44, September, 2006
	Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, ACM SIGCOMM Computer Communication Review, v.37 n.4, October 2007
	Yossi Azar , Iftah Gamzu , Shai Gutner, Truthful unsplittable flow for large capacity networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Keqin Li, Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks, Journal of Experimental Algorithmics (JEA), 12, June 2008
	A. Abouelaoualim , K. Ch. Das , L. Faria , Y. Manoussakis , C. Martinhon , R. Saad, Paths and trails in edge-colored graphs, Theoretical Computer Science, v.409 n.3, p.497-510, December, 2008
	Nikhil Bansal , Zachary Friggstad , Rohit Khandekar , Mohammad R. Salavatipour, A logarithmic approximation for unsplittable flow on line graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.702-709, January 04-06, 2009, New York, New York