### 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.

Original language | English |
---|---|

Title of host publication | Design and Analysis of Algorithms (First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings) |

Editors | G. Even, D. Rawitz |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 37-51 |

ISBN (Print) | 978-3-642-34861-7 |

DOIs | |

Publication status | Published - 2012 |

Event | conference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05 - Duration: 3 Dec 2012 → 5 Dec 2012 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 7659 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | conference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05 |
---|---|

Period | 3/12/12 → 5/12/12 |

Other | First Mediterranean Conference on Algorithms |

## Fingerprint Dive into the research topics of 'Multicast routing for energy minimization using speed scaling'. Together they form a unique fingerprint.

## Cite this

Bansal, N., Gupta, A., Krishnaswamy, R., Nagarajan, V., Pruhs, K. R., & Stein, C. (2012). Multicast routing for energy minimization using speed scaling. In G. Even, & D. Rawitz (Eds.),

*Design and Analysis of Algorithms (First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings)*(pp. 37-51). (Lecture Notes in Computer Science; Vol. 7659). Springer. https://doi.org/10.1007/978-3-642-34862-4_3