TY - CONF
AB - 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 such that 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 anytime 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 (FOCS 2005) in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive where dmax and lmin denote the largest di and the shortest available lease length, respectively. We also extend the SetCoverLeasing problem by deadlines and give a competitive online algorithm which also improves on existing solutions for the original SetCoverLeasing problem.
AU - Li, Shouwei
AU - Mäcker, Alexander
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 240
T2 - Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON)
TI - Towards Flexible Demands in Online Leasing Problems
ER -