Primal-dual approximation algorithms for the prize-collecting Steiner tree problem

DOI10.1016/J.IPL.2007.03.012zbMATH Open1184.68633OpenAlexW2099618932MaRDI QIDQ2379971FDOQ2379971

Authors: Paulo Feofiloff, Cristina G. Fernandes, José C. de Pina, Carlos E. Ferreira 

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.012

Recommendations

• Elementary approximation algorithms for prize collecting Steiner tree problems
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• scientific article; zbMATH DE number 1445375
• New primal-dual algorithms for Steiner tree problems
• Improved approximation algorithms for prize-collecting Steiner tree and TSP

zbMATH Keywords

approximation algorithmsprimal-dual methodprize-collecting Steiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Approximation algorithms for NP-hard problems.
• A General Approximation Technique for Constrained Forest Problems
• Title not available (Why is that?)
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• An efficient approximation algorithm for the survivable network design problem
• A data structure for bicategories, with application to speeding up an approximation algorithm
• A faster implementation of the Goemans-Williamson clustering algorithm

Cited In (21)

• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Risk models for the prize collecting Steiner tree problems with interval data
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Elementary approximation algorithms for prize collecting Steiner tree problems
• Complexity and approximation for traveling salesman problems with profits
• A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks
• An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
• Title not available (Why is that?)
• The fractional prize-collecting Steiner tree problem on trees (extended abstract)
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• Approximation algorithms for group prize-collecting and location-routing problems
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• A primal-dual approximation algorithm for the Steiner forest problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• New primal-dual algorithms for Steiner tree problems
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• Title not available (Why is that?)
• On the Exact Solution of Prize-Collecting Steiner Tree Problems

This page was built for publication: Primal-dual approximation algorithms for the prize-collecting Steiner tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379971)