TY - GEN
T1 - Hallucination helps
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms 2014
AU - Antoniadis, Antonios
AU - Im, Sungjin
AU - Krishnaswamy, Ravishankar
AU - Moseley, Benjamin
AU - Nagarajan, Viswanath
AU - Pruhs, Kirk
AU - Stein, Cliff
N1 - Conference code: 25
PY - 2014
Y1 - 2014
N2 - We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of a link is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power σ plus sα, where typically α ∊ [1.1,3]. We give a polynomial-time offline algorithm for multicommodity routing, that has approximation ratio O(loga k), where k is the number of demand pairs. This is obtained as a combination of three natural combinatorial algorithms. The key step of the algorithm design is a random sampling technique that we call hallucination, which is reminiscent of the Sample-Augment framework for solving Buy-at-Bulk type problems, and sampling in cut-sparsification algorithms. The analysis of the approximation ratio is then a direct consequence of the flow-cut gap for multicommodity flow. The algorithm extends rather naturally to an online algorithm, which we show has competitive ratio Õ(log3a+1 k). The analysis of the online algorithm introduces a natural “priority” multicommodity flow problem, and bounds the priority multicommodity flow-cut gap-this might also be of independent interest. We also explain how our hallucination technique can be used to achieve an (O(log km), O(logkm)) bicriteria approximation result for the problem of buying a minimum cost collection of unit-capacitated edges to support a concurrent multicommodity flow, where m is the number of links in the network.
AB - We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of a link is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power σ plus sα, where typically α ∊ [1.1,3]. We give a polynomial-time offline algorithm for multicommodity routing, that has approximation ratio O(loga k), where k is the number of demand pairs. This is obtained as a combination of three natural combinatorial algorithms. The key step of the algorithm design is a random sampling technique that we call hallucination, which is reminiscent of the Sample-Augment framework for solving Buy-at-Bulk type problems, and sampling in cut-sparsification algorithms. The analysis of the approximation ratio is then a direct consequence of the flow-cut gap for multicommodity flow. The algorithm extends rather naturally to an online algorithm, which we show has competitive ratio Õ(log3a+1 k). The analysis of the online algorithm introduces a natural “priority” multicommodity flow problem, and bounds the priority multicommodity flow-cut gap-this might also be of independent interest. We also explain how our hallucination technique can be used to achieve an (O(log km), O(logkm)) bicriteria approximation result for the problem of buying a minimum cost collection of unit-capacitated edges to support a concurrent multicommodity flow, where m is the number of links in the network.
KW - n/a OA procedure
U2 - 10.1137/1.9781611973402.84
DO - 10.1137/1.9781611973402.84
M3 - Conference contribution
SN - 978-1-611973-38-9
SP - 1141
EP - 1153
BT - Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
A2 - Chekuri, Chandra
PB - SIAM
Y2 - 5 January 2014 through 7 January 2014
ER -