1 Search Results for "Gao, Zhihan"

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.265

On Linear Programming Relaxations for Unsplittable Flow in Trees

Authors: Zachary Friggstad and Zhihan Gao

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

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)).

Cite as

Zachary Friggstad and Zhihan Gao. On Linear Programming Relaxations for Unsplittable Flow in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 265-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2015.265,
  author =	{Friggstad, Zachary and Gao, Zhihan},
  title =	{{On Linear Programming Relaxations for Unsplittable Flow in Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{265--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.265},
  URN =		{urn:nbn:de:0030-drops-53073},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.265},
  annote =	{Keywords: Unsplittable flow, Linear programming relaxation, Approximation algorithm}
}

Refine by Author
1 Friggstad, Zachary
1 Gao, Zhihan

Refine by Classification

Refine by Keyword
1 Approximation algorithm
1 Linear programming relaxation
1 Unsplittable flow

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Gao, Zhihan"

On Linear Programming Relaxations for Unsplittable Flow in Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message