Document Open Access Logo

Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs

Authors Jaroslaw Byrka, Mateusz Lewandowski, Carsten Moldenhauer

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.2.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Jaroslaw Byrka
Mateusz Lewandowski
Carsten Moldenhauer

Cite As Get BibTex

Jaroslaw Byrka, Mateusz Lewandowski, and Carsten Moldenhauer. Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.2

Abstract

We study the prize-collecting version of the node-weighted Steiner tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a 2.88-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev [6] for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain [17].

Subject Classification

Keywords
  • approximation algorithms
  • Node-Weighted Steiner Tree
  • primal-dual algorithm
  • LMP
  • planar graphs

Metrics

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

References

  1. Ajit Agrawal, Philip N. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. Google Scholar
  2. Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard J. Karloff. Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput., 40(2):309-332, 2011. Google Scholar
  3. MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, and Dániel Marx. Prize-collecting steiner problems on planar graphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1028-1049, 2011. Google Scholar
  4. MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, and Dániel Marx. Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011. Google Scholar
  5. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Improved approximation algorithms for (budgeted) node-weighted steiner problems. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 81-92, 2013. Google Scholar
  6. Piotr Berman and Grigory Yaroslavtsev. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 50-60, 2012. Google Scholar
  7. Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. An improved lp-based approximation for steiner tree. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 583-592, 2010. Google Scholar
  8. Jarosław Byrka, Mateusz Lewandowski, and Carsten Moldenhauer. Approximation algorithms for node-weighted prize-collecting steiner tree problems on planar graphs. CoRR, abs/1601.02481, 2016. Google Scholar
  9. Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Philip N. Klein. Node-weighted steiner tree and group steiner tree in planar graphs. ACM Trans. Algorithms, 10(3):13:1-13:20, 2014. Google Scholar
  10. Bistra N. Dilkina and Carla P. Gomes. Solving connected subgraph problems in wildlife conservation. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, 2010. Proceedings, pages 102-116, 2010. Google Scholar
  11. Karoline Faust, Pierre Dupont, Jérôme Callut, and Jacques van Helden. Pathway discovery in metabolic networks by subgraph extraction. Bioinformatics, 26(9):1211-1218, 2010. Google Scholar
  12. M. R. Garey and David S. Johnson. The rectilinear steiner tree problem in NP complete. SIAM Journal of Applied Mathematics, 32:826-834, 1977. Google Scholar
  13. Joseph Geunes, Retsef Levi, H. Edwin Romeijn, and David B. Shmoys. Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program., 130(1):85-106, 2011. Google Scholar
  14. Michel X. Goemans. Combining approximation algorithms for the prize-collecting TSP. CoRR, abs/0910.0553, 2009. Google Scholar
  15. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. Google Scholar
  16. Sudipto Guha, Anna Moss, Joseph Naor, and Baruch Schieber. Efficient recovery from power outage (extended abstract). In Proc. of the 31st Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 574-582, 1999. Google Scholar
  17. Mohammad Taghi Hajiaghayi and Kamal Jain. The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In Proc. of the 7th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA'06, pages 631-640, 2006. Google Scholar
  18. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  19. Jochen Könemann, Sina Sadeghian Sadeghabad, and Laura Sanità. An LMP o(log n)-approximation algorithm for node weighted prize collecting steiner tree. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 568-577, 2013. Google Scholar
  20. Carsten Moldenhauer. Primal-dual approximation algorithms for node-weighted steiner forest on planar graphs. Inf. Comput., 222:293-306, 2013. Google Scholar
  21. Carsten Moldenhauer. Node-weighted network design and maximum sub-determinants. PhD thesis, EPFL, 2014. Google Scholar
  22. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Google Scholar
  23. David Paul Williamson. On the design of approximation algorithms for a class of graph problems. PhD thesis, MIT, Cambridge, MA, September 1993. 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