Name
Abstract | ||
|---|---|---|
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 + 2radic(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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/AINAW.2007.266 | AINA Workshops (1) |
Keywords | Field | DocType |
previous algorithm,polynomial-time approximation algorithms,outstanding open question,approximation theory,polynomial-time approximation algorithm,possible ratio,minimum possible cost,approximation ratio,single-source multi-commodity flow problem,computational complexity,general version,single path,approximation algorithms,single-source unsplittable flow problem,minimum-cost single-source unsplittable flow,unsplittable flow.,telecommunication traffic,telecommunication network routing,new algorithms,educational technology,cost function,quality of service,bandwidth,polynomials,videoconference | Approximation algorithm,Mathematical optimization,Computer science,Flow (psychology),Approximation theory,Algorithm,Multi-commodity flow problem,Minimum-cost flow problem,Distributed computing,Computational complexity theory,Polynomial time approximation algorithm | Conference |
Volume | ISBN | Citations |
1 | 978-0-7695-2847-2 | 1 |
PageRank | References | Authors |
0.35 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chao Peng | 1 | 23 | 5.22 |
| Yasuo Tan | 2 | 151 | 25.41 |
| Laurence T. Yang | 3 | 6870 | 682.61 |