TY - GEN

T1 - Infrastructure leasing problems

AU - Anthony, Barbara M.

AU - Gupta, Anupam

PY - 2007

Y1 - 2007

N2 - Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets Dt ⊆ V for each day t ∈ [T]. A feasible solution to the problem is a set of edges E t for each t connecting Dt 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.

AB - Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets Dt ⊆ V for each day t ∈ [T]. A feasible solution to the problem is a set of edges E t for each t connecting Dt 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.

KW - Approximation algorithms

KW - Graph and network algorithms

KW - Randomized algorithms

KW - Stochastic combinatorial optimization

UR - http://www.scopus.com/inward/record.url?scp=38049052470&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049052470&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-72792-7_32

DO - 10.1007/978-3-540-72792-7_32

M3 - Conference contribution

AN - SCOPUS:38049052470

SN - 9783540727910

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 424

EP - 438

BT - Integer Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings

PB - Springer Verlag

T2 - 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII

Y2 - 25 June 2007 through 27 June 2007

ER -