Improved Approximation Algorithms for Unsplittable Flow Problems

In the single-source unsplittable flow problem we are given a graph G, a source vertex s and a set of sinks t/sub 1/, .. ., t/sub k/ with associated demands. We seek a single s-t/sub i/ flow path for each commodity i so that the demands are satisfied and the total flow routed across any edge e is bounded by its capacity c/sub e/. The problem is an NP-hard variant of max flow and a generalization of single-source edge-disjoint paths with applications to scheduling, load balancing and virtual-circuit routing problems. In a significant development, Kleinberg gave recently constant-factor approximation algorithms for several natural optimization versions of the problem. In this paper we give a generic framework, that yields simpler algorithms and significant improvements upon the constant factors. Our framework, with appropriate subroutines applies to all optimization versions previously considered and treats in a unified manner directed and undirected graphs.

Authors

• Stavros G. Kolliopoulos
• Cliff Stein 0001

Keywords

• Approximation algorithms
• Parallel machines
• Load management
• Routing
• Costs
• Testing
• Educational institutions
• Concurrent computing
• Engineering profession
• Processor scheduling
• Flow Problem
• Unsplittable Flow
• Undirected
• Constant Factor
• Maximum Flow
• Flow Path
• Partitioning Scheme
• Approximate Ratio
• Fractional Flow
• Makespan
• Partitioning Algorithm
• Minimum Capacity
• Performance Guarantees
• Fractional Solution
• Set Of Demands
• Flow Units
• Maximum Demand
• Arbitrary Network
• Source Vertex
• Minimum Cost Flow
• Optimal Metrics
• Amount Of Flow
• Constant Approximation
• Processing Time