文章基本信息

标题：On Linear Programming Relaxations for Unsplittable Flow in Trees
本地全文：下载
作者：Zachary Friggstad ; Zhihan Gao
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：265-283
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.265
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study some linear programming relaxations for the Unsplittable Flow problem on trees (UFP-Tree). Inspired by results obtained by Chekuri, Ene, and Korula for Unsplittable Flow on paths (UFP-Path), 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 efficiently-solvable relaxation for UFP-Tree with a sub-linear 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 demand-weighted subtrees of an edge-capacitated tree. On the other hand, we show that the inclusion of all rank constraints does not reduce the integrality gap for UFP-Tree 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 UFP-Path 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ász-Schrijver SDP procedure to the natural LP for UFP-Tree derives an SDP whose integrality gap is also O(log n * min(log m, log n)).
关键词：Unsplittable flow; Linear programming relaxation; Approximation algorithm