BCAM Seminar Routing for energy minimization in the speed scaling model
Fecha: Mié, Dic 9 2009
Ubicación: Universidad del País Vasco, Leioa, Spain / Ikerbasque Researcher
Ponentes: Volodymyr A. CHERNENKO
In this talk we consider a min-cost integer routing problem where the cost function represents the energy curve of a network element. Subadditive cost functions are well studied. We focus on theless-studied polynomial functions and polynomials with a startup cost.
The problem is interesting for two reasons. First, the cost function closely models the energy consumption of some network elements and network-wide optimization is a well-motivated but under-explored direction for energy minimization. Second, it brings light to a challenging combinatorial optimization problem. We will present positive and negative results for polynomial functions and polynomial functions with startup cost. For the latter, techniques to accomplish better-than-polynomial approximation ratios independent of demands and cost function remains a challenging problem.
Joint work with Matthew Andrews, Lisa Zhang, and Wenbo Zhao
The problem is interesting for two reasons. First, the cost function closely models the energy consumption of some network elements and network-wide optimization is a well-motivated but under-explored direction for energy minimization. Second, it brings light to a challenging combinatorial optimization problem. We will present positive and negative results for polynomial functions and polynomial functions with startup cost. For the latter, techniques to accomplish better-than-polynomial approximation ratios independent of demands and cost function remains a challenging problem.
Joint work with Matthew Andrews, Lisa Zhang, and Wenbo Zhao
Related events