TY - JOUR
T1 - Hallucination helps
T2 - Energy efficient virtual circuit routing
AU - Antoniadis, Antonios
AU - Im, Sungjin
AU - Krishnaswamy, Ravishankar
AU - Moseley, Benjamin
AU - Nagarajan, Viswanath
AU - Pruhs, Kirk
AU - Stein, Clifford
N1 - Funding Information:
\ast Received by the editors November 26, 2018; accepted for publication (in revised form) October 7, 2019; published electronically January 14, 2020. https://doi.org/10.1137/18M1228591 Funding: The first author was supported in part by DFG grant AN 1262/1-1. The second author was supported in part by NSF grants CCF-1409130, CCF-1617653, and CCF-1844939. The fourth author was supported in part by NSF grants CCF-1733873, CCF-1845146, and CCF 1824303 and a Google Faculty Award. The fifth author was supported in part by NSF grant CCF-1750127. The sixth author was supported in part by NSF grants CCF-1421508, CCF-1535755, CCF1907673, and an IBM Faculty Award. The seventh author was supported in part by NSF grants CCF-1421161 and CCF-1714818. \dagger Saarland University and Max-Planck-Institute for Informatics, 66123, Saarbru\"cken, Germany (antonios.antoniadis@mpiinf.mpg.de). \ddagger Electrical Engineering and Computer Science, University of California, Merced, Merced, CA 95343 (sim3@ucmerced.edu). \S Microsoft Research Vigyan Building, 9, Lavelle Road, Bangalore 560018 (ravishankar.k@gmail. com). \P Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213 (moseleyb85@ gmail.com). \| Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109 (viswa@umich.edu). \#Computer Science Department, University of Pittsburgh, Pittsburgh, PA 15260 (kirk@cs.pitt. edu). \dagger \dagger Department of IEOR, Columbia University, New York, NY 10027 (cliff@ieor.columbia.edu).
Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.
PY - 2020
Y1 - 2020
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 shut down when idle. We assume the standard model for component power: The power consumed by a component with load (speed) s is σ + sα , where σ is the static power and the exponent α > 1. We obtain a very simple O(logα k)-approximation algorithm for multicommodity routing, where k is the number of demand pairs. This improves upon previous results by several logarithmic factors. The key step in our algorithm is a random sampling technique that we call hallucination, which is reminiscent of the sample-augment framework for buy-at-bulk problems, and sampling in cut-sparsification algorithms. We also consider the online setting of the problem, where demand pairs arrive over time. We show that our offline algorithm naturally extends to the online setting, and obtain a randomized competitive ratio of O (log3α +1 k), which is the first nontrivial bound. The analysis of this algorithm involves the study of priority multicommodity flows, where edges and demand-pairs have priorities and each demandpair must route its flow only on edges of lower priority. We establish a polylogarithmic flow-cut gap for these priority flows, which we believe is of independent interest. Finally, we show how our technique can be used to achieve a randomized (O(logm),O(log2 m)) bicriteria competitive algorithm for the uniform capacitated network design problem, where m is the number of edges. Here, every edge has a cost ce and uniform capacity q, and the goal is to choose the minimum cost subgraph that can support the given multicommodity demand. This is the first online algorithm for this problem. In fact, our approach also improves prior results in the offline setting by several logarithmic factors.
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 shut down when idle. We assume the standard model for component power: The power consumed by a component with load (speed) s is σ + sα , where σ is the static power and the exponent α > 1. We obtain a very simple O(logα k)-approximation algorithm for multicommodity routing, where k is the number of demand pairs. This improves upon previous results by several logarithmic factors. The key step in our algorithm is a random sampling technique that we call hallucination, which is reminiscent of the sample-augment framework for buy-at-bulk problems, and sampling in cut-sparsification algorithms. We also consider the online setting of the problem, where demand pairs arrive over time. We show that our offline algorithm naturally extends to the online setting, and obtain a randomized competitive ratio of O (log3α +1 k), which is the first nontrivial bound. The analysis of this algorithm involves the study of priority multicommodity flows, where edges and demand-pairs have priorities and each demandpair must route its flow only on edges of lower priority. We establish a polylogarithmic flow-cut gap for these priority flows, which we believe is of independent interest. Finally, we show how our technique can be used to achieve a randomized (O(logm),O(log2 m)) bicriteria competitive algorithm for the uniform capacitated network design problem, where m is the number of edges. Here, every edge has a cost ce and uniform capacity q, and the goal is to choose the minimum cost subgraph that can support the given multicommodity demand. This is the first online algorithm for this problem. In fact, our approach also improves prior results in the offline setting by several logarithmic factors.
KW - Approximation algorithms
KW - Energy efficiency
KW - Network design
KW - Online algorithms
KW - n/a OA procedure
UR - http://www.scopus.com/inward/record.url?scp=85079817290&partnerID=8YFLogxK
U2 - 10.1137/18M1228591
DO - 10.1137/18M1228591
M3 - Article
AN - SCOPUS:85079817290
SN - 0097-5397
VL - 49
SP - 37
EP - 66
JO - SIAM journal on computing
JF - SIAM journal on computing
IS - 1
ER -