Document Open Access Logo

Stochastic Unsplittable Flows

Authors Anupam Gupta, Archit Karandikar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.7.pdf
  • Filesize: 0.58 MB
  • 19 pages

Document Identifiers

Author Details

Anupam Gupta
Archit Karandikar

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.7

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.
Keywords
  • Approximation Algorithms
  • Stochastic optimization
  • confluent flows
  • unsplittable flows

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 26-41, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.3.
  2. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012. Google Scholar
  3. Anand Bhalgat. A (2+ε)-approximation algorithm for the stochastic knapsack problem. At http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.222.7341&rep=rep1&type=pdf, 2011.
  4. Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved approximation results for stochastic knapsack problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1647-1665, 2011. Google Scholar
  5. Paul S. Bonsma, Jens Schulz, and Andreas Wiese. A constant factor approximation algorithm for unsplittable flow on paths. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 47-56, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.10.
  6. Gruia Calinescu, Amit Chakrabarti, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for resource allocation. ACM Trans. Algorithms, 7(4):Art. 48, 7, 2011. URL: http://dx.doi.org/10.1145/2000807.2000816.
  7. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. Approximation algorithms for the unsplittable flow problem. Algorithmica, 47(1):53-78, 2007. URL: http://dx.doi.org/10.1007/s00453-006-1210-5.
  8. Shuchi Chawla and Tim Roughgarden. Single-source stochastic routing. In Proceedings of APPROX, pages 82-94. Springer, 2006. Google Scholar
  9. Chandra Chekuri, Alina Ene, and Nitish Korula. Unsplittable flow in paths and trees and column-restricted packing integer programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pages 42-55, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03685-9_4.
  10. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An o(sqrt(n)) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137-146, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a007.
  11. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):Art. 27, 23, 2007. URL: http://dx.doi.org/10.1145/1273340.1273343.
  12. Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, and Adrian Vetta. (Almost) tight bounds and existence theorems for single-commodity confluent flows. J. ACM, 54(4):Art. 16, 32 pp. (electronic), 2007. URL: http://dx.doi.org/10.1145/1255443.1255444.
  13. Jiangzhuo Chen, Rajmohan Rajaraman, and Ravi Sundaram. Meet and merge: approximation algorithms for confluent flows. J. Comput. System Sci., 72(3):468-489, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.09.009.
  14. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In SODA, pages 395-404, 2005. Google Scholar
  15. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945-964, 2008. URL: http://dx.doi.org/10.1287/moor.1080.0330.
  16. Yefim Dinitz, Naveen Garg, and Michel X. Goemans. On the single-source unsplittable flow problem. Combinatorica, 19(1):17-41, 1999. URL: http://dx.doi.org/10.1007/s004930050043.
  17. Sudipto Guha and Kamesh Munagala. Approximation algorithms for budgeted learning problems. In ACM Symposium on Theory of Computing (STOC), pages 104-113. ACM, 2007. Full version as Sequential Design of Experiments via Linear Programming, URL: http://arxiv.org/abs/0805.2630v1.
  18. Sudipto Guha and Kamesh Munagala. Approximation algorithms for bayesian multi-armed bandit problems. CoRR, abs/1306.3525, 2013. URL: http://arxiv.org/abs/1306.3525.
  19. Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. Approximation algorithms for correlated knapsacks and non-martingale bandits. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 827-836, 2011. Google Scholar
  20. Archit Karandikar. Approximation algorithms for stochastic unsplittable flow problems. Master’s thesis, Carnegie Mellon University, 2015. URL: https://github.com/architkarandikar/MastersThesis.
  21. Jian Li and Wen Yuan. Stochastic combinatorial optimization via poisson approximation. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 971-980, 2013. URL: http://dx.doi.org/10.1145/2488608.2488731.
  22. Will Ma. Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: Extended abstract. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1154-1163, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.85.
  23. F. Bruce Shepherd and Adrian Vetta. The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. CoRR, abs/1504.00627, 2015. URL: http://arxiv.org/abs/1504.00627.
  24. F. Bruce Shepherd, Adrian Vetta, and Gordon T. Wilfong. Polylogarithmic approximations for the capacitated single-sink confluent flow problem. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 748-758, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.51.
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