Cluster Before You Hallucinate: Approximating Node-capacitated Network Design and Energy Efficient Routing

We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O(log³ n)- approximate with O(log⁴ n) congestion. This translates back to a O(log^4α+3 n)-approximation for the multicast energy-minimization routing problem, where α is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O(log⁵ n)-approximate with O(log¹² n) congestion, which translates back to a O(log^12α+5 n)-approximation for the unicast energy-minimization routing problem.