Online Network Leasing Problems

In the leasing optimization model, resources are leased for K different time periods, instead of being acquired for unlimited duration. The goal is to use these temporary resources to maintain a dynamic infrastructure that serves n requests while minimizing the total cost. We propose and study leasing variants of some network design problems. Currently we have an algorithm for the Online Connected Facility Leasing problem which is O(K lg n)-competitive if the scaling factor M = 1, and a O(lg K lg |V |)-competitive algorithm for the Online Steiner Network Leasing problem.