Document Open Access Logo

Non-Uniform Robust Network Design in Planar Graphs

Author David Adjiashvili

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.61.pdf
  • Filesize: 485 kB
  • 17 pages

Document Identifiers

Author Details

David Adjiashvili

Cite AsGet BibTex

David Adjiashvili. Non-Uniform Robust Network Design in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 61-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.61

Abstract

Robust optimization is concerned with constructing solutions that remain feasible also when a limited number of resources is removed from the solution. Most studies of robust combinatorial optimization to date made the assumption that every resource is equally vulnerable, and that the set of scenarios is implicitly given by a single budget constraint. This paper studies a robustness model of a different kind. We focus on Bulk-Robustness, a model recently introduced (Adjiashvili, Stiller, Zenklusen 2015) for addressing the need to model non-uniform failure patterns in systems. We significantly extend the techniques used by Adjiashvili et al. to design approximation algorithm for bulk-robust network design problems in planar graphs. Our techniques use an augmentation framework, combined with linear programming (LP) rounding that depends on a planar embedding of the input graph. A connection to cut covering problems and the dominating set problem in circle graphs is established. Our methods use few of the specifics of bulk-robust optimization, hence it is conceivable that they can be adapted to solve other robust network design problems.
Keywords
  • Robust optimization
  • Network design
  • Planar graph
  • Approximation algorithm
  • LP rounding

Metrics

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

References

  1. D. Adjiashvili. Structural Robustness in Combinatorial Optimization. PhD thesis, ETH Zürich, Zürich, Switzerland, 2012. Google Scholar
  2. D. Adjiashvili, G. Oriolo, and M. Senatore. The online replacement path problem. In Proceedings of 18th Annual European Symposium on Algorithms (ESA), pages 1-12. Springer, 2013. Google Scholar
  3. D. Adjiashvili, S. Stiller, and R. Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1-2):361-390, 2014. Google Scholar
  4. D. Adjiashvili and R. Zenklusen. An s-t connection problem with adaptability. Discrete Applied Mathematics, 159:695-705, 2011. Google Scholar
  5. H. Aissi, C. Bazgan, and D. Vanderpooten. Min–max and min–max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research, 197(2):427-438, 2009. Google Scholar
  6. N. Bansal and K. Pruhs. The geometry of scheduling. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 407-414, 2010. Google Scholar
  7. D. Bertsimas, D. B. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53:464-501, 2011. Google Scholar
  8. C. Chekuri, J. Vondrák, and R. Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1080-1097, 2011. Google Scholar
  9. J. Cheriyan and R. Thurimella. Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. SIAM J. Comput, 30:292-301, 2000. Google Scholar
  10. M. Damian-Iordache and S. V. Pemmaraju. A (2+ ε)-approximation scheme for minimum domination on circle graphs. Journal of Algorithms, 42(2):255-276, 2002. Google Scholar
  11. K. Dhamdhere, V. Goyal, R. Ravi, and M. Singh. How to pay, come what may: approximation algorithms for demand-robust covering problems. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 367-376, October 2005. Google Scholar
  12. U. Feige, K. Jain, M. Mahdian, and V. Mirrokni. Robust combinatorial optimization with exponential scenarios. In Matteo Fischetti and David Williamson, editors, IPCO 2007, volume 4513 of Lecture Notes in Computer Science, pages 439-453. Springer Berlin / Heidelberg, 2007. Google Scholar
  13. H. N. Gabow, M. X. Goemans, É. Tardos, and D. P. Williamson. Approximating the smallest k-edge connected spanning subgraph by lp-rounding. Networks, 53(4):345-357, 2009. Google Scholar
  14. H. N. Gabow, M.X. Goemans, and D.P. Williamson. An efficient approximation algorithm for the survivable network design problem. Mathematical Programming, Series B, 82(1-2):13-40, 1998. Google Scholar
  15. D. Golovin, V. Goyal, and R. Ravi. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. In Bruno Durand and Wolfgang Thomas, editors, STACS 2006, volume 3884 of Lecture Notes in Computer Science, pages 206-217. Springer Berlin / Heidelberg, 2006. Google Scholar
  16. F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146(1-2):525-554, 2014. Google Scholar
  17. V. Guruswami, S. Sachdeva, and R. Saket. Inapproximability of minimum vertex cover on k-uniform k-partite hypergraphs. SIAM Journal on Discrete Mathematics, 29(1):36-58, 2015. Google Scholar
  18. E. Israeli and R. K. Wood. Shortest-path network interdiction. Networks, 40:97-111, 2002. Google Scholar
  19. K. Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21:39-60, 2001. Google Scholar
  20. H. Kerivin and A.R. Mahjoub. Design of survivable networks: A survey. Networks, 46(1):1-21, 2005. Google Scholar
  21. R. Khandekar, G. Kortsarz, V. Mirrokni, and M. Salavatipour. Two-stage robust network design with exponential scenarios. In Dan Halperin and Kurt Mehlhorn, editors, ESA 2008, volume 5193 of Lecture Notes in Computer Science, pages 589-600. Springer Berlin / Heidelberg, 2008. Google Scholar
  22. P. Kouvelis and G. Yu. Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Boston., 1997. Google Scholar
  23. N.-K. Olver. Robust network design. PhD thesis, McGill University, Montreal, Quebec, Canada, 2010. Google Scholar
  24. C. H. Papadimitriou and M. Yannakakis. On the approximability of trade-offs and optimal access of web sources. In 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 86-92, 2000. Google Scholar
  25. R. Ravi, M. V. Marathe, Ravi S. S., Rosenkrantz D. J., and Hunt H. B. Many birds with one stone: Multi-objective approximation algorithms. In 25th annual ACM Symposium on the Theory of Computing (STOC), pages 438-447, 1993. Google Scholar
  26. D.P. Williamson, M.X. Goemans, M. Mihail, and V.V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435-454, 1995. Google Scholar
  27. G. Yu and J. Yang. On the robust shortest path problem. Computers & Operations Research, 25(6):457-468, 1998. Google Scholar
  28. R. Zenklusen. Matching interdiction. Discrete Applied Mathematics, 158(15):1676-1690, 2010. 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 Imprint Privacy Contact