Fast approximation algorithms for multicommodity flow problems
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-comodity minimum-cost flow problems, and the first polynomial-time combinatorial algorithms for approximately solving the multicommodation flow problem are described.
Abstract
Article Free Access Share on Fast approximation algorithms for multicommodity flow problems Authors: Tom Leighton Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MAView Profile , Clifford Stein Laboratory for Computer Science, MIT, Cambridge, MA Laboratory for Computer Science, MIT, Cambridge, MAView Profile , Fillia Makedon Computer Science Program, University of Texas at Dallas, Richardson, Texas Computer Science Program, University of Texas at Dallas, Richardson, TexasView Profile , Éva Tardos School of Operations Research, Cornell University, Ithaca, NY School of Operations Research, Cornell University, Ithaca, NYView Profile , Serge Plotkin Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile , Spyros Tragoudas Computer Science Program, University of Texas at Dallas, Richardson, Texas Computer Science Program, University of Texas at Dallas, Richardson, TexasView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 101–111https://doi.org/10.1145/103418.103425Online:03 January 1991Publication History 62citation759DownloadsMetricsTotal Citations62Total Downloads759Last 12 Months17Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF