Multicommodity demand flow in a tree (extended abstract)

We consider requests for capacity in a given tree network T = (V, E) where each edge of the tree has some integer capacity u_e. Each request consists of an integer demand d_f and a profit w_f which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provide a maximum profit. This generalizes well-known problems including the knapsack and b-matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg, Vazirani, and Yannakakis [5] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. In this paper we establish for the first time that the natural linear programming relaxation has a constant factor gap, a factor of 4, for the case of arbitrary profits. We then discuss the situation for arbitrary demands. When the maximum demand d_max is at most the minimum edge capacity u_min, we show that the integrality gap of the LP is at most 48. This result is obtained showing that the integrality gap for demand version of such a problem is at most 12 times that for the unit demand case. We use techniques of Kolliopoulos and Stein [8,9] to obtain this. We also obtain, via this method, improved algorithms for the line and ring networks. Applications and connections to other combinatorial problems are discussed.