Infrastructure leasing problems

Barbara M. Anthony, Anupam Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540727910
StatePublished - 2007
Event12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, United States
Duration: Jun 25 2007Jun 27 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4513 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
Country/TerritoryUnited States
CityIthaca, NY


  • Approximation algorithms
  • Graph and network algorithms
  • Randomized algorithms
  • Stochastic combinatorial optimization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Infrastructure leasing problems'. Together they form a unique fingerprint.

Cite this