1 Search Results for "Gupta, Divya"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.267
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees

Authors: Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We study the Unsplittable Flow Problem (UFP) and related variants, namely UFP with Bag Constraints and UFP with Rounds, on paths and trees. We provide improved constant factor approximation algorithms for all these problems under the no bottleneck assumption (NBA), which says that the maximum demand for any source-sink pair is at most the minimum capacity of any edge. We obtain these improved results by expressing a feasible solution to a natural LP relaxation of the UFP as a near-convex combination of feasible integral solutions.
Cite as

Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 267-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{elbassioni_et_al:LIPIcs.FSTTCS.2012.267,
  author =	{Elbassioni, Khaled and Garg, Naveen and Gupta, Divya and Kumar, Amit and Narula, Vishal and Pal, Arindam},
  title =	{{Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{267--275},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.267},
  URN =		{urn:nbn:de:0030-drops-38650},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.267},
  annote =	{Keywords: Approximation Algorithms, Integer Decomposition, Linear Programming, Scheduling, Unsplittable Flows}
}
  • Refine by Author
  • 1 Elbassioni, Khaled
  • 1 Garg, Naveen
  • 1 Gupta, Divya
  • 1 Kumar, Amit
  • 1 Narula, Vishal
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Integer Decomposition
  • 1 Linear Programming
  • 1 Scheduling
  • 1 Unsplittable Flows

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact