Hallucination helps: Energy efficient virtual circuit routing

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (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 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.

Original languageEnglish
Pages (from-to)37-66
Number of pages30
JournalSIAM journal on computing
Issue number1
Publication statusPublished - 2020
Externally publishedYes


  • Approximation algorithms
  • Energy efficiency
  • Network design
  • Online algorithms
  • n/a OA procedure


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

    Antoniadis, A., Im, S., Krishnaswamy, R., Moseley, B., Nagarajan, V., Pruhs, K. & Stein, C., 2014, Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Chekuri, C. (ed.). SIAM, p. 1141-1153 13 p.

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

    7 Citations (Scopus)

Cite this