Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing
From MaRDI portal
Publication:5259609
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.
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
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(7)- Minimum-cost network design with (dis)economies of scale
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
- Hallucination helps: energy efficient virtual circuit routing
- Multicast routing for energy minimization using speed scaling
- Hallucination helps: energy efficient virtual circuit routing
- Energy-efficient network routing with discrete cost functions
- Dealing with residual energy when transmitting data in energy-constrained capacitated networks
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)
