Infrastructure Leasing Problems

摘要

Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets D_t is contained in V for each day t ∈ [T]. A feasible solution to the problem is a set of edges Et for each t connecting D_t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we lease edges for say, { a day, a week, a month, a year }. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.