Access Restriction

Author Du, Jingde ♦ Kolliopoulos, Stavros G.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Approximation algorithms ♦ Network flow ♦ Unsplittable flow
Abstract In the single-source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain sinks in a given graph with edge capacities. The demand of each commodity must be routed along a single path so that the total flow through any edge is at most, its capacity. This problem was introduced by Kleinberg [1996a] and generalizes several NP-complete problems. A cost value per unit of flow may also be defined for every edge. In this paper, we implement the 2-approximation algorithm of Dinitz et al. [1999] for congestion, which is the best known, and the (3, 1)-approximation algorithm of Skutella [2002] for congestion and cost, which is the best known bicriteria approximation. We experimentally study the quality of approximation achieved by the algorithms and the effect of heuristics on their performance. We also compare these algorithms against the previous best ones by Kolliopoulos and Stein [1999].
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 10

Open content in new tab

   Open content in new tab
Source: ACM Digital Library