1 Search Results for "Karandikar, Archit"


Document
Stochastic Unsplittable Flows

Authors: Anupam Gupta and Archit Karandikar

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


Abstract
We consider the stochastic unsplittable flow problem: given a graph with edge-capacities, and source-sink pairs with each pair having a size and a value, the goal is to route the pairs unsplittably while respecting edge capacities to maximize the total value of the routed pairs. However, the size of each pair is a random variable and is revealed only after we decide to route that pair. Which pairs should we route, along which paths, and in what order so as to maximize the expected value? We present results for several cases of the problem under the no-bottleneck assumption. We show a logarithmic approximation algorithm for the single-sink problem on general graphs, considerably improving on the prior results of Chawla and Roughgarden which worked for planar graphs. We present an approximation to the stochastic unsplittable flow problem on directed acyclic graphs, within less than a logarithmic factor of the best known approximation in the non-stochastic setting. We present a non-adaptive strategy on trees that is within a constant factor of the best adaptive strategy, asymptotically matching the best results for the non-stochastic unsplittable flow problem on trees. Finally, we give results for the stochastic unsplittable flow problem on general graphs. Our techniques include using edge-confluent flows for the single-sink problem in order to control the interaction between flow-paths, and a reduction from general scheduling policies to "safe" ones (i.e., those guaranteeing no capacity violations), which may be of broader interest.

Cite as

Anupam Gupta and Archit Karandikar. Stochastic Unsplittable Flows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.APPROX-RANDOM.2017.7,
  author =	{Gupta, Anupam and Karandikar, Archit},
  title =	{{Stochastic Unsplittable Flows}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  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.2017.7},
  URN =		{urn:nbn:de:0030-drops-75569},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.7},
  annote =	{Keywords: Approximation Algorithms, Stochastic optimization, confluent flows, unsplittable flows}
}
  • Refine by Author
  • 1 Gupta, Anupam
  • 1 Karandikar, Archit

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Stochastic optimization
  • 1 confluent flows
  • 1 unsplittable flows

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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