loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st International Conference on Advanced Information Networking and Applications Workshops (AINAW'07)
New Algorithms for the Minimum-Cost Single-Source Unsplittable Flow Problem
Niagara Falls, Ontario, Canada
May 21-May 23
ISBN: 0-7695-2847-3
Chao Peng, Japan Advanced Institute of Science and Technology, Japan
Yasuo Tan, Japan Advanced Institute of Science and Technology, Japan
Laurence T. Yang, St. Francis Xavier University, Canada
The Minimum-Cost Single-Source Unsplittable Flow problem is a Single-Source multi-commodity flow problem in which each commodity should be shipped only on one single path at the minimum possible cost without violating the capacity of each edge. An outstanding open question on this problem is whether a simultaneous (2,1)--approximation can be achieved for minimizing congestion and cost. But for the general version so far the best possible ratio is (3+2\sqrt 2, 1).. In this paper we present a polynomial-time approximation algorithms which achieves this approximation ratio, our algorithm is more efficient and easier to implement compares to previous algorithms for this problem.
Index Terms:
Approximation Algorithms; Unsplittable Flow.
Citation:
Chao Peng, Yasuo Tan, Laurence T. Yang, "New Algorithms for the Minimum-Cost Single-Source Unsplittable Flow Problem," ainaw, vol. 1, pp.136-141, 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.