Barman, Siddharth ;
Chawla, Shuchi ;
Umboh, Seeun
Network Design with Coverage Costs
Abstract
We study network design with a cost structure motivated by redundancy in data traffic. We are given a graph, g groups of terminals, and a universe of data packets. Each group of terminals desires a subset of the packets from its respective source. The cost of routing traffic on any edge in the network is proportional to the total size of the distinct packets that the edge carries. Our goal is to find a minimum cost routing. We focus on two settings. In the first, the collection of packet sets desired by sourcesink pairs is laminar. For this setting, we present a primaldual based 2approximation, improving upon a logarithmic approximation due to Barman and Chawla (2012){BC12}. In the second setting, packet sets can have nontrivial intersection. We focus on the case where each packet is desired by either a single terminal group or by all of the groups. This setting does not admit an O(log^{{1}/{4}  gamma} g)approximation for any constant gamma under a standard assumption; we present an O(log g)approximation when the graph is unweighted.
Our approximation for the second setting is based on a novel spannertype construction in unweighted graphs that, given a collection of g vertex subsets, finds a subgraph of cost only a constant factor more than the minimum spanning tree of the graph, such that every subset in the collection has a Steiner tree in the subgraph of cost at most O(log g) that of its minimum Steiner tree in the original graph. We call such a subgraph a group spanner.
BibTeX  Entry
@InProceedings{barman_et_al:LIPIcs:2014:4687,
author = {Siddharth Barman and Shuchi Chawla and Seeun Umboh},
title = {{Network Design with Coverage Costs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {4863},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4687},
URN = {urn:nbn:de:0030drops46876},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.48},
annote = {Keywords: Network Design, Spanner, Primal Dual Method, Traffic Redundancy}
}
04.09.2014
Keywords: 

Network Design, Spanner, Primal Dual Method, Traffic Redundancy 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 