A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria

Full text

Pdf (1.32 MB)

Source

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

El Paso, Texas, United States

Pages: 636 - 643

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Aravind Srinivasan	Dept. of Information Systems & Computer Science, National University of Singapore, Singapore 119260, Republic of Singapore
Chung-Piaw Teo	Department of Decision Sciences, National University of Singapore, Singapore 119260, Republic of Singapore

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 28, Citation Count: 10

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/258533.258658 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	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	J. Beck and J. H. Spencer. Integral approximation sequences. Mathematical Programming, 30:88-98, 1984.
	3	D. Bertsimas and R. Vohra. Linear programming relaxations, approximation algorithms and randomization; a unified view of covering problems. Technical Report OR 285-94, MIT, 1994.
	4	R. Cole , B. Maggs , R. Sitaraman, Routing on butterfly networks with random faults, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.558, October 23-25, 1995
	5	G. Dobson. Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Mathematics of Operations Research, 7:515-531, 1982.
	6	M. L. Fisher and L. A. Wolsey. On the greedy heuristic for continuous coveting and packing problems. SIAMJ. on Algebraic and Discrete Methods, 3:584-591, 1982.
	7	C. M. Fortuin, J. Ginibre, and P. N. Kasteleyn. Correlational inequalities for partially ordered sets. Communications of Mathematical Physics, 22:89--103, 1971.
	8	D. R. Fulkerson. Blocking Polyhedra. In Graph Theory and Its Applications, B. Harris, ed., Academic Press, 93-112, 1970.
	9	C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. B. Rao, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proc. IEEE Symposium on Foundations of Computer Science, pages 285-296, 1990.
	10	R. M. Karp, F. T. Leighton, R. L. Rivest, C. D. Thompson, U. V. Vazirani, and V. V. Vazirani. Global wire routing in twodimensional arrays. Algorithmica, 2:113-129, 1987.
	11	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	12	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
	13	F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica, 14:167-186, 1994.
	14	F. T. Leighton, B. M. Maggs, and A. Richa. Fast algorithms for finding O(congestion+dilation) packet routing schedules. Technical Report CMU-CS-96-152, School of Computer Science, Carnegie-Mellon University, 1996. To appear in Combinatorica.
	15	F. T Leighton, B. M. Maggs, and R. Sitaraman. On the fault tolerance of some popular bounded-degree networks. In Proc. IEEE Symposium on Foundations of Computer Science, pages 542-552, 1992.
	16	F.T. Leighton and S. B. Rao. An approximate max-flow mincut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. IEEE Symposium on Foundations of Computer Science, pages 422--431, 1988.
	17	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	18	Madhav V. Marathe , R. Ravi , Ravi Sundaram, Service-constrained network design problems, Nordic Journal of Computing, v.3 n.4, p.367-387, Winter 1996
	19	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	20	Moni Naor , Ron M. Roth, Optimal File Sharing in Distributed Networks, SIAM Journal on Computing, v.24 n.1, p.158-183, Feb. 1995 [doi>10.1137/S0097539792237462]
	21	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	22	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
	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	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	25	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167209]
	26	David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
	27	Aravind Srinivasan, Improved approximations of packing and covering problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.268-276, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225138]
	28	L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11:350-361, 1982.
	29	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

CITED BY 10

	David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States
	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Multicasting in heterogeneous networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.448-453, May 24-26, 1998, Dallas, Texas, United States
	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States
	Matthew Andrews , Lisa Zhang, Packet routing with arbitrary end-to-end delay requirements, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.557-565, May 01-04, 1999, Atlanta, Georgia, United States
	V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	William Aiello , Rafail Ostrovsky , Eyal Kushilevitz , Adi Rosén, Dynamic routing on networks with fixed-size buffers, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Costas Busch , Malik Magdon-Ismail , Jing Xi, Oblivious routing on geometric networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Matthew Andrews , Antonio Fernández , Ashish Goel , Lisa Zhang, Source routing and scheduling in packet networks, Journal of the ACM (JACM), v.52 n.4, p.582-601, July 2005
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007