Strongly Polynomial Algorithms for the Unsplittable Flow Problem

摘要: We provide the first strongly polynomial algorithms with best approximation ratio for all three variants of unsplittable flow problem (UFP). In this we are given a (possibly directed) capacitated graph n vertices and m edges, set terminal pairs each its own demand profit. The objective is to connect subset by single path as maximize total profit satisfied subject capacity constraints. Classical UFP, in which demands must be lower than edge capacities, known have an O(√m) algorithm. same result combinatorial extended UFP case when some might higher capacities. For that both improve current use algorithms. also bound show provably harder classical case. last variant bounded where at most 1/K minimum capacity. Using here well, currently Specifically, K = 2 our results better thereby separating two problems.