Document Open Access Logo

Improved Algorithms for Scheduling Unsplittable Flows on Paths

Authors Hamidreza Jahanjou, Erez Kantor, Rajmohan Rajaraman

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.49.pdf
  • Filesize: 0.85 MB
  • 12 pages

Document Identifiers

Author Details

Hamidreza Jahanjou
Erez Kantor
Rajmohan Rajaraman

Cite AsGet BibTex

Hamidreza Jahanjou, Erez Kantor, and Rajmohan Rajaraman. Improved Algorithms for Scheduling Unsplittable Flows on Paths. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.49

Abstract

In this paper, we investigate offline and online algorithms for Round-UFPP, the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform sizes on a given path with non-uniform edge capacities. Round-UFPP is NP-hard and constant-factor approximation algorithms are known under the no bottleneck assumption (NBA), which stipulates that maximum size of a flow is at most the minimum edge capacity. We study Round-UFPP without the NBA, and present improved online and offline algorithms. We first study offline Round-UFPP for a restricted class of instances called alpha-small, where the size of each flow is at most alpha times the capacity of its bottleneck edge, and present an O(log(1/(1 - alpha)))-approximation algorithm. Our main result is an online O(log log cmax)-competitive algorithm for Round-UFPP for general instances, where cmax is the largest edge capacities, improving upon the previous best bound of O(log cmax) due to [16]. Our result leads to an offline O(min(log n, log m, log log cmax))- approximation algorithm and an online O(min(log m, log log cmax))-competitive algorithm for Round-UFPP, where n is the number of flows and m is the number of edges.
Keywords
  • Approximation algorithms
  • Online algorithms
  • Unsplittable flows
  • Interval coloring
  • Flow scheduling

Metrics

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

References

  1. Udo Adamy and Thomas Erlebach. Online coloring of intervals with bandwidth. In Klaus Jansen and Roberto Solis-Oba, editors, Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, volume 2909 of Lecture Notes in Computer Science, pages 1-12. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-24592-6_1.
  2. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+eps approximation for unsplittable flow on a path. CoRR, abs/1211.2670, 2012. Google Scholar
  3. Esther M. Arkin and Ellen B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1):1 - 8, 1987. Google Scholar
  4. E. Asplund and B. Grünbaum. On a coloring problem. Mathematica Scandinavica, 8(0):181-188, 1960. Google Scholar
  5. Yossi Azar, Amos Fiat, Meital Levy, and N. S. Narayanaswamy. An improved algorithm for online coloring of intervals with bandwidth. Theor. Comput. Sci., 363(1):18-27, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.06.014.
  6. Nikhil Bansal, Amit Chakrabarti, Amir Epstein, and Baruch Schieber. A quasi-ptas for unsplittable flow on line graphs. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 721-729. ACM, 2006. URL: http://dx.doi.org/10.1145/1132516.1132617.
  7. Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R. Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 702-709. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496847.
  8. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, September 2001. Google Scholar
  9. Mark Bartlett, Alan M. Frisch, Youssef Hamadi, Ian Miguel, Armagan Tarim, and Chris Unsworth. The temporal knapsack problem and its solution. In Roman Barták and Michela Milano, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Second International Conference, CPAIOR 2005, Prague, Czech Republic, May 30 - June 1, 2005, Proceedings, volume 3524 of Lecture Notes in Computer Science, pages 34-48. Springer, 2005. URL: http://dx.doi.org/10.1007/11493853_5.
  10. P. Bonsma, J. Schulz, and A. Wiese. A constant factor approximation algorithm for unsplittable flow on paths. In FOCS'11, pages 47-56, 2011. Google Scholar
  11. Gruia Calinescu, Amit Chakrabarti, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for resource allocation. ACM Trans. Algorithms, 7(4):48:1-48:7, September 2011. Google Scholar
  12. Parinya Chalermsook. Coloring and maximum independent set of rectangles. APPROX'11, pages 123-134, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0_11.
  13. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, ICALP'03, pages 410-425, 2003. Google Scholar
  14. Andreas Darmann, Ulrich Pferschy, and Joachim Schauer. Resource allocation with time intervals. Theoretical Computer Science, 411(49):4217 - 4234, 2010. Google Scholar
  15. Khaled M. Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. Approximation algorithms for the unsplittable flow problem on paths and trees. In Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18 of LIPIcs, pages 267-275. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.267.
  16. Leah Epstein, Thomas Erlebach, and Asaf Levin. Online capacitated interval coloring. SIAM Journal on Discrete Mathematics, 23(2):822-841, 2009. Google Scholar
  17. Leah Epstein and Meital Levy. Online interval coloring and variants. In ICALP'05, pages 602-613, 2005. Google Scholar
  18. N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. Google Scholar
  19. H. A. Kierstead. The linearity of first-fit coloring of interval graphs. SIAM Journal on Discrete Mathematics, 1(4):526-530, 1988. Google Scholar
  20. H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33:143-153, 1981. Google Scholar
  21. Alexandr Kostochka. Coloring intersection graphs of geometric figures with a given clique number. In Contemporary Mathematics 342, AMS, 2004. Google Scholar
  22. Cynthia A. Phillips, R. N. Uma, and Joel Wein. Off-line admission control for general scheduling problems. In Journal of Scheduling, pages 879-888, 2000. Google Scholar
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