Back to Search
Start Over
CLUSTER BEFORE YOU HALLUCINATE: NODE-CAPACITATED NETWORK DESIGN AND ENERGY EFFICIENT ROUTING.
- Source :
-
SIAM Journal on Computing . 2024, Vol. 53 Issue 3, p588-623. 36p. - Publication Year :
- 2024
-
Abstract
- 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]
- Subjects :
- *APPROXIMATION algorithms
*NETWORK routers
*UNDIRECTED graphs
*STATISTICAL sampling
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 53
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 178376526
- Full Text :
- https://doi.org/10.1137/20M1360645