Leasing with Uncertainty

Theoretical study of real-life leasing scenarios was initiated in 2005 with a simple leasing model defined as follows. Demands arrive with time and need to be served by leased resources. Different types of leases are available, each with a fixed duration and price, respecting economy of scale (longer leases cost less per unit time). An algorithm is to lease resources at minimum possible costs in order to serve each arriving demand, without knowing future demands. In this paper, we generalize this model and introduce the Lease-or-Decline and Lease-or-Delay leasing models. In the Lease-or-Decline model, not all demands need to be served, i.e., the algorithm may decline a demand as long as a penalty associated with it is paid. In the Lease-or-Delay model, each demand has a deadline and can be served any day before its deadline as long as a penalty is paid for each delayed day. The goal is to minimize the total cost of purchased leases and penalties paid. For each of these models we give a deterministic online primal-dual algorithm, evaluated using the standard competitive analysis in which an online algorithm is compared to the optimal offline algorithm which knows the entire sequence of demands in advance and is optimal.