Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Improved Algorithms for Scheduling Unsplittable Flows on Paths

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We investigate offline and online algorithms for \(\mathsf {Round}\text {-}\mathsf {UFPP}\), the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. \(\mathsf {Round}\text {-}\mathsf {UFPP}\) is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for \(\mathsf {Round}\text {-}\mathsf {UFPP}\) without the NBA. We first study offline \(\mathsf {Round}\text {-}\mathsf {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. Next, our main result is an online \(O(\log \log c_{\max })\)-competitive algorithm for \(\mathsf {Round}\text {-}\mathsf {UFPP}\)  where \(c_{\max }\) is the largest edge capacity, improving upon the previous best bound of \(O(\log c_{\max })\) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline \(O(\min (\log n, \log m, \log \log c_{\max }))\)-approximation algorithm and an online \(O(\min (\log m, \log \log c_{\max }))\)-competitive algorithm for \(\mathsf {Round}\text {-}\mathsf {UFPP}\), where n is the number of flows and m is the number of edges.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Clearly, in the case of paths and trees, the term is redundant. We use the terminology \(\mathsf {UFPP}\) to be consistent with the prior work in this area.

  2. Not to be confused with \(\mathsf {Round}\text {-}\mathsf {UFPP}\) where the graph is restricted to be a path.

References

  1. Adamy, U., Erlebach, T.: Online coloring of intervals with bandwidth. In: Solis-Oba, R., Jansen, K. (eds.) Approximation and Online Algorithms, pp. 1–12. Springer, Berlin (2004)

    MATH  Google Scholar 

  2. Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing 2+eps approximation for unsplittable flow on a path. CoRR arXiv:1211.2670 (2012)

  3. Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18(1), 1–8 (1987)

    Article  MATH  Google Scholar 

  4. Asplund, E., Grünbaum, B.: On a coloring problem. Math. Scand. 8, 181–188 (1960)

    Article  MATH  Google Scholar 

  5. Aumann, Y., Rabani, Y.: Improved bounds for all optical routing. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’95, pp. 567–576. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1995)

  6. Azar, Y., Fiat, A., Levy, M., Narayanaswamy, N.: An improved algorithm for online coloring of intervals with bandwidth. Theor. Comput. Sci. 363(1), 18–27 (2006)

    Article  MATH  Google Scholar 

  7. Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC’06, pp. 721–729 (2006)

  8. Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA’09, pp. 702–709 (2009)

  9. Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)

    Article  MATH  Google Scholar 

  10. Bartlett, M., Frisch, A.M., Hamadi, Y., Miguel, I., Tarim, S.A., Unsworth, C.: The temporal knapsack problem and its solution. In: CPAIOR’05, pp. 34–48. Springer, Berlin (2005)

  11. Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: FOCS’11, pp. 47–56 (2011)

  12. Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7(4), 48:1-48:7 (2011)

    Article  MATH  Google Scholar 

  13. Chalermsook, P.: Coloring and maximum independent set of rectangles. In: APPROX. RANDOM 2011. Lecture Notes in Computer Science, vol. 6845. Springer, Berlin (2011)

  14. Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. Lecture Notes in Computer Science, vol. 2719. Springer, Berlin

  15. Darmann, A., Pferschy, U., Schauer, J.: Resource allocation with time intervals. Theoret. Comput. Sci. 411(49), 4217–4234 (2010)

    Article  MATH  Google Scholar 

  16. Elbassioni, K.M., Garg, N., Gupta, D., Kumar, A., Narula, V., Pal, A.: Approximation algorithms for the unsplittable flow problem on paths and trees. In: FSTTCS’12, pp. 267–275 (2012)

  17. Epstein, L., Erlebach, T., Levin, A.: Online capacitated interval coloring. SIAM J. Discrete Math. 23(2), 822–841 (2009)

    Article  MATH  Google Scholar 

  18. Epstein, L., Levy, M.: Online interval coloring and variants. In: ICALP 2005. Lecture Notes in Computer Science, vol. 3580. Springer, Berlin

  19. Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)

    Article  MATH  Google Scholar 

  20. Golumbic, M.C., Lipshteyn, M., Stern, M.: Edge intersection graphs of single bend paths on a grid. Networks 54(3), 130–138 (2009). https://doi.org/10.1002/net.20305

    Article  MATH  Google Scholar 

  21. Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1(4), 526–530 (1988)

    Article  MATH  Google Scholar 

  22. Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numer. 33, 143–153 (1981)

    MATH  Google Scholar 

  23. Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. In: Contemporary Mathematics, vol. 342. AMS (2004)

  24. Kumar, S.R., Panigrahy, R., Russell, A., Sundaram, R.: A note on optical routing on trees. Inf. Process. Lett. 62(6), 295–300 (1997)

    Article  MATH  Google Scholar 

  25. Mihail, M., Kaklamanis, C., Rao, S.: Efficient access to optical bandwidth wavelength routing on directed fiber trees, rings, and trees of rings. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 548–557 (1995)

  26. Phillips, C.A., Uma, R.N., Wein, J.: Off-line admission control for general scheduling problems. J. Sched. 3, 879–888 (2000)

    Article  MATH  Google Scholar 

  27. Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, pp. 134–143. ACM, New York, NY, USA (1994)

  28. Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103–128 (2007)

    Article  MATH  Google Scholar 

Download references

Funding

Funding was provided by National Science Foundation (Grant No. CCF-1422715) and Office of Naval Research.

Author information

Authors and Affiliations

  1. Northeastern University, San Jose, CA, USA

    Hamidreza Jahanjou

  2. Akamai Technologies Inc., Cambridge, MA, USA

    Erez Kantor

  3. Northeastern University, Boston, MA, USA

    Rajmohan Rajaraman

Authors
  1. Hamidreza Jahanjou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erez Kantor
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rajmohan Rajaraman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hamidreza Jahanjou.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A previous version of this paper has appeared in the proceedings of ISAAC 2017.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jahanjou, H., Kantor, E. & Rajaraman, R. Improved Algorithms for Scheduling Unsplittable Flows on Paths. Algorithmica 85, 563–583 (2023). https://doi.org/10.1007/s00453-022-01043-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-022-01043-6

Keywords

Search

Navigation