A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
Document Open Access Logo

A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs

Authors Zachary Friggstad, Jochen Könemann, Mohammad Shadravan

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.3.pdf
  • Filesize: 0.49 MB
  • 11 pages

Document Identifiers

Author Details

Zachary Friggstad
Jochen Könemann
Mohammad Shadravan

Cite As Get BibTex

Zachary Friggstad, Jochen Könemann, and Mohammad Shadravan. A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.3

Abstract

We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is O(log k) in quasi-bipartite graphs with k terminals. Such instances can be seen to generalize set cover, so the integrality gap analysis is tight up to a constant factor.  A novel aspect of our approach is that we use the primal-dual method; a technique that is rarely used in designing approximation algorithms for network design problems in directed graphs.

Subject Classification

Keywords
  • Approximation algorithm
  • Primal-Dual algorithm
  • Directed Steiner tree

Metrics

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

References

  1. J. Byrka, F. Grandoni, T. Rothvoss, , and L. Sanita. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1), 2013. Google Scholar
  2. G. Calinescu and G. Zelikovsky. The polymatroid steiner problems. J. Combinatorial Optimization, 9(3):281-294, 2005. Google Scholar
  3. M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, , and M. Li. Approximation algorithms for directed steiner problems. J. Algorithms, 33(1):73-91, 1999. Google Scholar
  4. I. Dinur and D. Steurer. Analytic approach to parallel repetition. In In proceedings of STOC, 2014. Google Scholar
  5. J. Edmonds. Optimum branchings. J. Res. Natl. Bur. Stand., 71:233-240, 1967. Google Scholar
  6. U. Feige. A threshold of ln n for approximating set-cover. Journal of the ACM, 45(4):634-652, 1998. Google Scholar
  7. Z. Friggstad, A. Louis, Y. K. Ko, J. Könemann, M. Shadravan, and M. Tulsiani. Linear programming hierarchies suffice for directed steiner tree. In In proceedings of IPCO, 2014. Google Scholar
  8. M. X. Goemans, N. Olver, T. Rothvoss, and R. Zenklusen. Matroids and integrality gaps for hypergraphic steiner tree relaxations. In In proceedings of STOC, 2012. Google Scholar
  9. M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  10. S. Guha, A. Moss, J. Naor, and B. Scheiber. Efficient recover from power outage. In In proceedings of STOC, 1999. Google Scholar
  11. E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability. In In proceedings of STOC, 2003. Google Scholar
  12. T. Hibi and T. Fujito. Multi-rooted greedy approximation of directed steiner trees with applications. In In proceedings of WG, 2012. Google Scholar
  13. C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982. Google Scholar
  14. S. Rajagopalan and V. V. Vazirani. On the bidirected cut relaxation for the metric steiner tree problem. In In proceedings of SODA, 1999. Google Scholar
  15. T. Rothvoss. Directed steiner tree and the lasserre hierarchy. Technical report, CORR abs/1111.5473, 2011. Google Scholar
  16. V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2003. Google Scholar
  17. A. Zelikovsky. A series of approximation algorthms for the acyclic directed steiner tree problem. Algorithmica, 18:99-110, 1997. Google Scholar
  18. L. Zosin and S. Khuller. On directed steiner trees. In In proceedings of SODA, 2002. 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