Multicommodity demand flow in a tree and packing integer programs

URL:

http://portal.acm.org/citation.cfm?doid=1273340.1273343

Keywords:

Integer multicommodity flow; tree; integrality gap; packing integer program; approximation algorithm

Abstract:

We consider the multicommodity all-or-nothing flow problem in a tree. We are given a tree with integer edge capacities u(e) and a set F of demand edges f=uv, each with an integer d(f). A subset of demands is routable if no edge capacity is violated after each demand sends d(f) units of flow between its endpoints. Special cases of this problem include when the tree is a single edge (knapsack problem), when the tree is a star (demand matching problem) and when all demands are 1 (integer multicommodity flow on a tree), or when the tree is a line (interval packing), and when the tree is a star (the b-matching problem). For the unit demand case, Garg, Vazarani and Yannakis gave a 2-approximation for the the maximum cardinality problem. We show that the integrality gap for the weighted (unit demand) case is at most 4. Following, Cheriyan, Jordan, and Ravi, we ask whether this can be brought down to 3/2 (thus generalizing Shannon's multigraph edge colouring result). Our result together with a technique of Kolliopoulos and Stein can then be used to show that for general demands, a gap of at most 48 holds (the first constant factor for this problem).