Cluster before you hallucinate

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

Ravishankar Krishnaswamy, Clifford Stein, Kirk Pruhs, Viswanath Nagarajan

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• 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 (1)

• Minimum-Cost Network Design with (Dis)economies of Scale

Uses Software

• SuLQ

This page was built for publication: Cluster before you hallucinate

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