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  ⊆ V for each day t ∈ [T]. A feasible solution to the problem is a set of edges E t 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.