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

Please wait, while we are loading the content...

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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Zhang, Lisa Antonakopoulos, Spyridon Andrews, Matthew
Copyright Year	2016
Abstract	Given a network, a set of demands, and a cost function $f(\cdot)$, the min-cost network design problem is to route all demands with the objective of minimizing $\sum_e f(\ell_e)$, where $\ell_e$ is the total traffic load under the routing. We focus on cost functions of the form $f(x)= \sigma + x^{\alpha}$ for $x > 0$, with $f(0) = 0$. For $\alpha \le 1$, $f(\cdot)$ is subadditive. This case corresponds to the well-studied buy-at-bulk network design problem and admits polylogarithmic approximation and hardness. In this paper, we focus on the less-studied scenario of $\alpha > 1$ with a positive start-up cost $\sigma > 0$. Now, the cost function $f(\cdot)$ is neither subadditive nor superadditive. It aims to model a range of computing and communication devices for which doubling processing speed more than doubles their power consumption. We begin by discussing why existing routing techniques such as randomized rounding and tree-metric embedding fail to generalize directly. We then present our main contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitated min-cost flow problem that we believe is interesting in its own right. Our approach for this problem builds upon the well-linked decomposition due to Chekuri, Khanna, and Shepherd [Proceedings of ACM STOC, ACM, New York, pp. 183--192], the construction of expanders via matchings due to Khandekar, Rao, and Vazirani [J. ACM, 56 (2009), 19], and edge-disjoint routing in well-connected graphs due to Rao and Zhou [SIAM J. Comput., 39 (2010), pp. 1856--1887]. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.
Starting Page	49
Ending Page	66
Page Count	18
File Format	PDF
ISSN	00975397
DOI	10.1137/110825959
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-01-07
Access Restriction	Subscribed
Subject Keyword	energy-efficient networks Analysis of algorithms and problem complexity diseconomies of scale approximation algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design

Approximating the Single-Sink Link-Installation Problem in Network Design

Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

Approximating Minimum Cost Connectivity Orientation and Augmentation

Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem

Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees

Message Multicasting in Heterogeneous Networks

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

Similar Documents

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

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design

Approximating the Single-Sink Link-Installation Problem in Network Design

Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

Approximating Minimum Cost Connectivity Orientation and Augmentation

Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem

Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees

Message Multicasting in Heterogeneous Networks

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