Hallucination helps: energy efficient virtual circuit routing

Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsChandra Chekuri
Number of pages13
ISBN (Electronic)978-1-61197-340-2
ISBN (Print)978-1-611973-38-9
Publication statusPublished - 2014
Externally publishedYes
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms 2014 - Portland, United States
Duration: 5 Jan 20147 Jan 2014
Conference number: 25


Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms 2014
Country/TerritoryUnited States


  • n/a OA procedure


Dive into the research topics of 'Hallucination helps: energy efficient virtual circuit routing'. Together they form a unique fingerprint.

Cite this