Skip to main content
SpringerLink
Log in

Improved algorithms for resource allocation under varying capacity

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the well-studied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.

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

Access this article

Log in via an institution

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
Fig. 6
Fig. 7

Similar content being viewed by others

References

  • Adamaszek, A., & Wiese, A. (2013). Approximation schemes for maximum weight independent set of rectangles. In 54th Annual IEEE symposium on foundations of computer science, FOCS (pp. 400–409).

  • Adamaszek, A., Chalermsook, P., Ene, A., & Wiese, A. (2016). Submodular unsplittable flow on trees. In Proceedings of the 18th conference on integer programming and combinatorial optimization (IPCO).

  • Agarwal, P., Kreveld, M., & Suri, S. (1998). Label placement by maximum independent set in rectangles. Computational Geometry, 11(3–4), 209–218.

    Article  Google Scholar 

  • Akcoglu, K., Aspnes, J., Dasgupta, B., & Kao, M. (2000). Opportunity cost algorithms for combinatorial auctions. In E. Kontoghiorghes, B. Rustem, & S. Siokos (Eds.), Applied optimization: Computational methods in decision-making, economics and finance (pp. 455–476) Kluwer Academic Publishers.

  • Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2013). Constant integrality gap LP formulations of unsplittable flow on a path. In Proceedings of the 16th international conference on integer programming and combinatorial optimization (IPCO) (pp. 25–36).

  • Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Wiese, A. (2014). A mazing \(2+\epsilon \) approximation for Unsplittable Flow on a Path. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 26–41).

  • Bansal, N., Chakrabarti, A., Epstein, A., & Schieber, B. (2006). A quasi-PTAS for unsplittable flow on line graphs. In Proceedings of the 38th annual ACM symposium on theory of computing, STOC (pp. 721–729).

  • Bansal, N., Friggstad, Z., Khandekar, R., & Salavatipour, M. (2009). A logarithmic approximation for unsplittable flow on line graphs. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 702–709).

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

    Article  Google Scholar 

  • Bar-Noy, A., Guha, S., Noar, J., & Schieber, B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing SICOMP, 31(2), 331–352.

    Article  Google Scholar 

  • Berman, P., & Dasgupta, B. (2000). Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3), 307–323.

    Article  Google Scholar 

  • Bonsma, P., Schulz, J., & Wiese, A. (2011). A constant factor approximation algorithm for unsplittable flow on paths. In IEEE 52nd annual symposium on foundations of computer science, FOCS (pp. 47–56).

  • Calinescu, G., Chakrabarti, A., Karloff, H. J., & Rabani, Y. (2002). Improved approximation algorithms for resource allocation. In Integer programming and combinatorial optimization, 9th International IPCO (pp. 401–414).

  • Chakaravarthy, V., Choudhury, A. R., & Sabharwal, Y. (2010). A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints. In IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS (pp. 181–191).

  • Chakaravarthy, V., Choudhury, A., Roy, S., & Sabharwal, Y. (2013). Distributed algorithms for scheduling on line and tree networks with non-uniform bandwidths. In 27th IEEE international symposium on parallel and distributed processing, IPDPS (pp. 973–984).

  • Chakaravarthy, V., Pandit, V., Sabharwal, Y., & Seetharam, D. (2010). Varying bandwidth resource allocation problem with bag constraints. In 24th IEEE international symposium on parallel and distributed processing, IPDPS (pp. 1–10).

  • Chakaravarthy, V., Roy, S., & Sabharwal, Y. (2012). Distributed algorithms for scheduling on line and tree networks. In ACM symposium on principles of distributed computing, PODC (pp. 345–354).

  • Chakrabarti, A., Chekuri, C., Gupta, A., & Kumar, A. (2007). Approximation algorithms for the unsplittable flow problem. Algorithmica, 47(1), 53–78.

    Article  Google Scholar 

  • Chalermsook, P., & Chuzhoy, J. (2009). Maximum independent set of rectangles. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 892–901).

  • Chekuri, C., Ene, A., & Korula, N. (2009). Unsplittable flow in paths and trees and column-restricted packing integer programs. In Proceedings of the 12th international workshop on approximation, randomization, and combinatorial optimization (APPROX) (pp.42–55).

  • Chekuri, C., Mydlarz, M., & Shepherd, F. (2007). Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3(3), 27. doi:10.1145/1273340.1273343.

  • Chuzhoy, J., Ostrovsky, R., & Rabani, Y (2001). Approximation algorithms for the job interval selection problem and related scheduling problems. In 42nd Annual symposium on foundations of computer science, FOCS (pp. 348–356).

  • Elbassioni, K., Garg, N., Gupta, D., Kumar, A., Narula, V., & Pal, A. (2012). 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 (pp. 267–275).

  • Erlebach, T., & Spieksma, F. (2003). Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, 46(1), 27–53.

    Article  Google Scholar 

  • Fowler, R., Paterson, M., & Tanimoto, S. (1981). Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3), 133–137.

    Article  Google Scholar 

  • Grandoni, F., Ingala, S., & Uniyal, S. (2013). Improved approximation algorithms for unsplittable flow on a path with time windows. In Proceedings of the 13th workshop on approximation and online algorithms (pp. 25–36).

  • Khanna, S., Muthukrishnan, S., & Paterson, M. (1998). On approximating rectangle tiling and packing. In Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms, SODA (pp. 384–393).

  • Kolliopoulos, S. (2007). Edge-disjoint paths and unsplittable flow. In T. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics. London: Chapman and Hall.

    Google Scholar 

  • Panconesi, A., & Sozio, M. (2010). Fast primal-dual distributed algorithms for scheduling and matching problems. Distributed Computing, 22(4), 269–283.

    Article  Google Scholar 

  • Spieksma, F. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2, 215–227.

    Article  Google Scholar 

  • Ye, Y., & Borodin, A. (2012). Elimination graphs. ACM Transactions on Algorithms, 8(2), 14.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Research, New Delhi, India

    Venkatesan T. Chakaravarthy, Anamitra R. Choudhury & Yogish Sabharwal

  2. University of Illinois at Urbana-Champaign, Champaign, IL, USA

    Shalmoli Gupta

  3. Linkedin, Bangalore, India

    Sambudha Roy

Authors
  1. Venkatesan T. Chakaravarthy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anamitra R. Choudhury
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shalmoli Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sambudha Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yogish Sabharwal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Venkatesan T. Chakaravarthy.

Additional information

A preliminary version of the paper appeared in the proceedings of ESA 2014. Research conducted while Shalmoli Gupta and Sambudha Roy were at IBM Research, India.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chakaravarthy, V.T., Choudhury, A.R., Gupta, S. et al. Improved algorithms for resource allocation under varying capacity. J Sched 21, 313–325 (2018). https://doi.org/10.1007/s10951-017-0515-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-017-0515-3

Keywords

Search

Navigation