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 -