@inproceedings{1492f2a079c64b349fbefdcf214625f3,

title = "Multicast routing for energy minimization using speed scaling",

abstract = "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 s¿+¿fa, where s is the static power, and a¿>¿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 polynomial-time O(a)-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.",

author = "N. Bansal and Anupam Gupta and R. Krishnaswamy and V. Nagarajan and K.R. Pruhs and C. Stein",

year = "2012",

doi = "10.1007/978-3-642-34862-4_3",

language = "English",

isbn = "978-3-642-34861-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "37--51",

editor = "G. Even and D. Rawitz",

booktitle = "Design and Analysis of Algorithms (First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings)",

address = "Germany",

note = "conference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05 ; Conference date: 03-12-2012 Through 05-12-2012",

}