Startseite > Publikationen > Publikationen


Li, Shouwei;Markarian, Christine;Meyer auf der Heide, Friedhelm:

Towards Flexible Demands in Online Leasing Problems.

Algorithmica 80(5): S. 1556-1574, Jan. 2018 -


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 ai and its deadline ai+di 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 di=0 for all i. We propose an online algorithm that is Θ(K+dmax/lmin)-competitive, where dmax and lmin denote the largest di 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 O(log(m*(K+dmax/lmin))log(lmax))-competitive randomized algorithm, where m represents the number of subsets and lmax represents the largest available lease length. This improves on existing solutions for the original SetCoverLeasing problem. For the latter, we give an O((K+dmax/lmin)log(lmax))-competitive deterministic algorithm.


author = {Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm},
title = {Towards Flexible Demands in Online Leasing Problems},
journal = {Algorithmica},
volume = {80},
number = {5},
pages = {1556-1574},
month = jan,
year = {2018},
note = {},

BibTeX in die Zwischenablage kopieren