Abstract
We study some linear programming relaxations for the Unsplittable Flow problem on trees (UFPTree). Inspired by results obtained by Chekuri, Ene, and Korula for Unsplittable Flow on paths (UFPPath), we present a relaxation with polynomially many constraints that has an integrality gap bound of O(log n * min(log m, log n)) where n denotes the number of tasks and m denotes the number of edges in the tree. This matches the approximation guarantee of their combinatorial algorithm and is the first demonstration of an efficientlysolvable relaxation for UFPTree with a sublinear integrality gap.
The new constraints in our LP relaxation are just a few of the (exponentially many) rank constraints that can be added to strengthen the natural relaxation. A side effect of how we prove our upper bound is an efficient O(1)approximation for solving the rank LP. We also show that our techniques can be used to prove integrality gap bounds for similar LP relaxations for packing demandweighted subtrees of an edgecapacitated tree.
On the other hand, we show that the inclusion of all rank constraints does not reduce the integrality gap for UFPTree to a constant. Specifically, we show the integrality gap is Omega(sqrt(log n)) even in cases where all tasks share a common endpoint. In contrast, intersecting instances of UFPPath are known to have an integrality gap of O(1) even if just a few of the rank 1 constraints are included.
We also observe that applying two rounds of the LovĂˇszSchrijver SDP procedure to the natural LP for UFPTree derives an SDP whose integrality gap is also O(log n * min(log m, log n)).
BibTeX  Entry
@InProceedings{friggstad_et_al:LIPIcs:2015:5307,
author = {Zachary Friggstad and Zhihan Gao},
title = {{On Linear Programming Relaxations for Unsplittable Flow in Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {265283},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5307},
URN = {urn:nbn:de:0030drops53073},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.265},
annote = {Keywords: Unsplittable flow, Linear programming relaxation, Approximation algorithm}
}
Keywords: 

Unsplittable flow, Linear programming relaxation, Approximation algorithm 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) 
Issue Date: 

2015 
Date of publication: 

13.08.2015 