Document Open Access Logo

Network Design with Coverage Costs

Authors Siddharth Barman, Shuchi Chawla, Seeun Umboh

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.48.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Siddharth Barman
Shuchi Chawla
Seeun Umboh

Cite As Get BibTex

Siddharth Barman, Shuchi Chawla, and Seeun Umboh. Network Design with Coverage Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 48-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.48

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 source-sink pairs is laminar. For this setting, we present a primal-dual based 2-approximation, improving upon a logarithmic approximation due to Barman and Chawla (2012){BC12}. In the second setting, packet sets can have non-trivial 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 spanner-type 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.

Subject Classification

Keywords
  • Network Design
  • Spanner
  • Primal Dual Method
  • Traffic Redundancy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ashok Anand, Vyas Sekar, and Aditya Akella. SmartRE: an architecture for coordinated network-wide redundancy elimination. In ACM SIGCOMM, 2009. Google Scholar
  2. M. Andrews and L. Zhang. Bounds on fiber minimization in optical networks with fixed fiber capacity. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 1, pages 409-419 vol. 1, March 2005. Google Scholar
  3. Matthew Andrews. Hardness of buy-at-bulk network design. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 115-124. IEEE, 2004. Google Scholar
  4. Matthew Andrews and Lisa Zhang. Approximation algorithms for access network design. Algorithmica, 34(2):197-215, 2002. Google Scholar
  5. Baruch Awerbuch and Yossi Azar. Buy-at-bulk network design. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, pages 542-547, 1997. Google Scholar
  6. Baruch Awerbuch, Alan Baratz, and David Peleg. Cost-sensitive analysis of communication protocols. In Proceedings of the ninth annual ACM symposium on Principles of distributed computing, PODC'90, pages 177-187, New York, NY, USA, 1990. ACM. Google Scholar
  7. Siddharth Barman and Shuchi Chawla. Traffic-redundancy aware network design. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'12, pages 1487-1498. SIAM, 2012. Google Scholar
  8. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS'96, pages 184-193, Washington, DC, USA, 1996. IEEE Computer Society. Google Scholar
  9. BlueCoat: WAN Optimization. URL: http://www.bluecoat.com.
  10. Michael Elkin and David Peleg. (1+ε,β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608-631, 2004. Google Scholar
  11. Paul Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publ. House Czechoslovak Acad. Sci., Prague, 1964. Google Scholar
  12. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448-455, 2003. Google Scholar
  13. M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  14. S. Guha, A. Meyerson, and K. Munagala. Hierarchical placement and network design problems. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pages 603-612, 2000. Google Scholar
  15. Anupam Gupta, Amit Kumar, Martin Pál, and Tim Roughgarden. Approximation via cost-sharing: A simple approximation algorithm for the multicommodity rent-or-buy problem. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS'03, pages 606-617, 2003. Google Scholar
  16. Anupam Gupta, Amit Kumar, and Tim Roughgarden. Simpler and better approximation algorithms for network design. In STOC'03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 365-372, 2003. Google Scholar
  17. A. Hayrapetyan, C. Swamy, and É. Tardos. Network design for information networks. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 933-942. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  18. Samir Khuller, Balaji Raghavachari, and Neal Young. Balancing minimum spanning and shortest path trees. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, SODA'93, pages 243-250, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics. Google Scholar
  19. Amit Kumar, Anupam Gupta, and Tim Roughgarden. A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS'02, pages 333-344, 2002. Google Scholar
  20. F Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the 42nd ACM symposium on Theory of computing, pages 47-56. ACM, 2010. Google Scholar
  21. Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Cost-distance: Two metric network design. SIAM J. Comput., 38(4):1648-1659, December 2008. Google Scholar
  22. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 3-12. IEEE, 2009. Google Scholar
  23. Seth Pettie. Low distortion spanners. In Automata, Languages and Programming, pages 78-89. Springer, 2007. Google Scholar
  24. Riverbed Networks: WAN Optimization. URL: http://www.riverbed.com/us/solutions/optimization.
  25. David B. Shmoys, Chaitanya Swamy, and Retsef Levi. Facility location with service installation costs. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1088-1097, 2004. Google Scholar
  26. Neil T. Spring and David Wetherall. A protocol-independent technique for eliminating redundant network traffic. In Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication - SIGCOMM'00, pages 87-95, Stockholm, Sweden, 2000. Google Scholar
  27. Zoya Svitkina and Éva Tardos. Facility location with hierarchical facility costs. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 153-161, 2006. Google Scholar
  28. Kunal Talwar. The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap. In Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, pages 475-486, 2002. Google Scholar
  29. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, January 2005. Google Scholar
  30. Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 802-809. ACM, 2006. Google Scholar
  31. Vijay V Vazirani. Approximation Algorithms. Springer, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact