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

Towards Flexible Demands in Online Leasing Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems in which a resource can be leased for K different durations each incurring a different cost (longer leases cost less per time unit). Each demand i can be served any time between its arrival \(a_i\) and its deadline \(a_i + d_i\) by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s ParkingPermitProblem (in: Proceedings of the 46th annual IEEE symposium on foundations of computer science, FOCS ’05, IEEE Computer Society, Washington, pp 274–284, 2005) in which \(d_i=0\) for all i. We propose an online algorithm that is \(\varTheta (K + \frac{d_\textit{max}}{l_\textit{min}})\)-competitive, where \(d_\textit{max}\) and \(l_\textit{min}\) denote the largest \(d_i\) and the shortest available lease length, respectively. We also extend SetCoverLeasing and FacilityLeasing to their respective variants in which deadlines are added. For the former, we give an \(\mathcal {O}\left( \log (m \cdot (K + \frac{d_\textit{max}}{l_\textit{min}}))\log l_\textit{max} \right) \)-competitive randomized algorithm, where m represents the number of subsets and \(l_\textit{max}\) represents the largest available lease length. This improves on existing solutions for the original SetCoverLeasing problem. For the latter, we give an \(\mathcal {O}\left( (K + \frac{d_\textit{max}}{l_\textit{min}})\log l_{\text {max}} \right) \)-competitive deterministic algorithm.

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

Similar content being viewed by others

References

  1. Abshoff, S., Kling, P., Markarian, C., Meyer auf der Heide, F., Pietrzyk, P.: Towards the price of leasing online. J. Comb. Optim. 32(4), 1197–1216 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  2. Abshoff, S., Markarian, C., Meyer auf der Heide, F.: Randomized online algorithms for set cover leasing problems. In: Combinatorial Optimization and Applications—8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, 19–21 December 2014, Proceedings, pp. 25–34 (2014)

  3. Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361–370 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.S.: A general approach to online network optimization problems. ACM Trans. Algorithms 2(4), 640–660 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  5. Alon, N., Azar, Y., Gutner, S.: Admission control to minimize rejections and online set cover with repetitions. In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’05, pp. 238–244. ACM, New York (2005)

  6. Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2), 153–177 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Anthony, B.M., Gupta, A.: Infrastructure leasing problems. In: IPCO, pp. 424–438 (2007)

  8. Ausiello, G., Giannakos, A., Paschos, V.T.: Greedy algorithms for online set covering and related problems. In: Proceedings of the Twelfth Computing: The Australasian Theory Symposium—vol. 51, CATS ’06, pp. 145–151. Australian Computer Society, Inc., Darlinghurst (2006)

  9. Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, 19–22 October 1997, pp. 542–547 (1997)

  10. Berman, P., DasGupta, B.: Approximating the online set multicover problems via randomized winnowing. Theor. Comput. Sci. 393(1–3), 54–71 (2008)

    Article  MATH  Google Scholar 

  11. Berman, P., DasGupta, B., Sontag, E.D.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(6–7), 733–749 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bhawalkar, K., Gollapudi, S., Panigrahi, D.: Online set cover with set requests. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, 4–6 September 2014, Barcelona, Spain, pp. 64–79 (2014)

  13. Buchbinder, N., Naor, J.: Online primal–dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270–286 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207–222 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  16. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  17. Fotakis, D.: On the competitive ratio for online facility location. In: Proceedings of the 30th International Conference on Automata, Languages and Programming, ICALP’03, pp. 637–652. Springer, Berlin (2003)

  18. Fotakis, D.: A primal–dual algorithm for online non-uniform facility location. J. Discrete Algorithms 5(1), 141–148 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  19. Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, 16–18 September 2003, Revised Papers, pp. 137–150 (2003)

  20. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98, pp. 649–657. Society for Industrial and Applied Mathematics, Philadelphia (1998)

  21. Gupta, A., Kumar, A., Pál, M., Roughgarden, T.: Approximation via cost sharing: simpler and better approximation algorithms for network design. J. ACM 54(3), 11 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  22. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795–824 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  23. Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal–dual schema and Lagrangian relaxation. J. ACM 48(2), 274–296 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  24. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  25. Kling, P., Meyer auf der Heide, F., Pietrzyk, P.: An algorithm for online facility leasing. In: Structural Information and Communication Complexity—19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30–July 2, 2012, Revised Selected Papers, pp. 61–72 (2012)

  26. Korman, S.: On the use of randomization in the online set cover problem. Master’s thesis, Weizmann Institute of Science, Rehovot (2004)

  27. Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of the 38th International Conference on Automata, Languages and Programming—Volume Part II, ICALP’11, pp. 77–88. Springer, Berlin (2011)

  28. Li, S., Mäcker, A., Markarian, C., Meyer auf der Heide, F., Riechers, S.: Towards flexible demands in online leasing problems. In: Computing and Combinatorics—21st International Conference, COCOON 2015, Beijing, China, 4–6 August 2015, Proceedings, pp. 277–288 (2015)

  29. Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383–390 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  30. Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229–242 (2002)

  31. Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816–832 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  32. Meyerson, A.: Online facility location. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS ’01, pp. 426–431. IEEE Computer Society, Washington (2001)

  33. Meyerson, A.M.: The parking permit problem. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’05, pp. 274–284. IEEE Computer Society, Washington (2005)

  34. Nagarajan, C., Williamson, D.P.: Offline and online facility leasing. Discrete Optim. 10(4), 361–370 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  35. Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Buy-at-bulk network design: approximating the single-sink edge installation problem. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’97, pp. 619–628. Society for Industrial and Applied Mathematics, Philadelphia (1997)

  36. Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pp. 265–274. ACM, New York (1997)

  37. Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Heinz Nixdorf Institute, University of Paderborn, Fürstenallee 11, 33102, Paderborn, Germany

    Shouwei Li, Christine Markarian & Friedhelm Meyer auf der Heide

Authors
  1. Shouwei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christine Markarian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Friedhelm Meyer auf der Heide
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christine Markarian.

Additional information

The results presented in this paper are based on the conference paper [28]. This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center ‘On-The-Fly Computing’ (SFB 901).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, S., Markarian, C. & Meyer auf der Heide, F. Towards Flexible Demands in Online Leasing Problems. Algorithmica 80, 1556–1574 (2018). https://doi.org/10.1007/s00453-018-0420-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-018-0420-y

Keywords

Search

Navigation