CLUSTER BEFORE YOU HALLUCINATE: NODE-CAPACITATED NETWORK DESIGN AND ENERGY EFFICIENT ROUTING.

We consider the following node-capacitated network design problem. The input is an undirected graph, a set of demands, uniform node capacity, and arbitrary node costs. The goal is to find a minimum node-cost subgraph that supports all demands concurrently subject to the node capacities. We consider both single- and multicommodity demands and provide the first polylogarithmic approximation guarantees. For single-commodity demands (i.e., all request pairs have the same sink node), we obtain an O(log²n) approximation to the cost with an O(log³n) factor violation in node capacities. For multicommodity demands, we obtain an O(log4n) approximation to the cost with an O(log10n) factor violation in node capacities. We use a variety of techniques, including single-sink confluent flows, low-load set cover, random sampling, and cut-sparsification. We also develop new techniques for clustering multicommodity demands into (nearly) node-disjoint clusters, which may be of independent interest. Moreover, this network design problem has applications to energy-efficient virtual circuit routing. In this setting, there is a network of routers that are speed scalable and that may be shut down when idle. We assume the standard model for power: the power consumed by a router with load (speed) s is \sigma + s\alpha, where \sigma is the static power and the exponent \alpha > 1. We obtain the first polylogarithmic approximation algorithms for this problem when speed-scaling occurs on nodes of a network. [ABSTRACT FROM AUTHOR]