TY - GEN
T1 - Multicast Routing for Energy Minimization Using Speed Scaling
AU - Bansal, Nikhil
AU - Gupta, Anupam
AU - Krishnaswamy, Ravishankar
AU - Nagarajan, Viswanath
AU - Pruhs, Kirk
AU - Stein, Cliff
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2012.
PY - 2012
Y1 - 2012
N2 - We consider virtual circuit multicast routing in a network of links that are speed scalable. We assume that a link with load f uses power σ + fα,whereσ is the static power, and α>1 is some constant. We assume that a link may be shutdown if not in use. In response to the arrival of client i at vertex ti a routing path (the virtual circuit) Pi connecting a fixed source s to sink ti must be established. The objective is to minimize the aggregate power used by all links. We give a polylog-competitive online algorithm, and a polynomialtime O(α)-approximation offline algorithm if the power functions of all links are the same. If each link can have a different power function, we show that the problem is APX-hard. If additionally, the edges may be directed, then we show that no poly-log approximation is possible in polynomial time under standard complexity assumptions. These are the first results on multicast routing in speed scalable networks in the algorithmic literature.
AB - We consider virtual circuit multicast routing in a network of links that are speed scalable. We assume that a link with load f uses power σ + fα,whereσ is the static power, and α>1 is some constant. We assume that a link may be shutdown if not in use. In response to the arrival of client i at vertex ti a routing path (the virtual circuit) Pi connecting a fixed source s to sink ti must be established. The objective is to minimize the aggregate power used by all links. We give a polylog-competitive online algorithm, and a polynomialtime O(α)-approximation offline algorithm if the power functions of all links are the same. If each link can have a different power function, we show that the problem is APX-hard. If additionally, the edges may be directed, then we show that no poly-log approximation is possible in polynomial time under standard complexity assumptions. These are the first results on multicast routing in speed scalable networks in the algorithmic literature.
UR - http://www.scopus.com/inward/record.url?scp=84902120010&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902120010&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34862-4_3
DO - 10.1007/978-3-642-34862-4_3
M3 - Conference contribution
AN - SCOPUS:84902120010
SN - 9783642348617
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 51
BT - Design and Analysis of Algorithms - 1st Mediterranean Conference on Algorithms, MedAlg 2012, Proceedings
A2 - Even, Guy
A2 - Rawitz, Dror
PB - Springer Science and Business Media Deutschland GmbH
T2 - 1st Mediterranean Conference on Algorithms, MedAlg 2012
Y2 - 3 December 2012 through 5 December 2012
ER -