Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

DOI10.1145/2591796.2591831zbMATH Open1315.68287arXiv1403.6207OpenAlexW2052361350MaRDI QIDQ5259609FDOQ5259609

Authors: Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Clifford Stein 

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. We consider both multicast routing and unicast routing. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O(log^3n)-approximate with O(log^4 n) congestion. This translates back to a O(log ^(4{alpha}+3) n)-approximation for the multicast energy-minimization routing problem, where {alpha} is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O(log^5 n)-approximate with O(log^12 n) congestion, which translates back to a O(log^(12{alpha}+5) n)-approximation for the unicast energy-minimization routing problem.

Full work available at URL: https://arxiv.org/abs/1403.6207

Recommendations

• Hallucination helps: energy efficient virtual circuit routing
• Approximation algorithms for a capacitated network design problem
• Multicast routing for energy minimization using speed scaling
• Hallucination helps: energy efficient virtual circuit routing
• Energy-efficient network routing with discrete cost functions

zbMATH Keywords

approximation algorithmsnetwork designmulticommodity flowsenergy efficient routing

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Cites Work

• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower bounds in differential privacy
• Iterative Constructions and Private Data Release
• Differential privacy and the fat-shattering dimension of linear queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Title not available (Why is that?)
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• Title not available (Why is that?)
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the sample complexity for private learning and private data release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (3)

• Multicast routing for energy minimization using speed scaling
• Minimum-Cost Network Design with (Dis)economies of Scale
• Energy-efficient network routing with discrete cost functions

Uses Software

• SuLQ

This page was built for publication: Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259609)