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

DOI10.1016/J.IPL.2007.03.012MaRDI QIDQ2379971zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsprimal-dual methodprize-collecting Steiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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

Cites work

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

Cited in

(24)

• On the Exact Solution of Prize-Collecting Steiner Tree Problems
• Risk models for the prize collecting Steiner tree problems with interval data
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Elementary approximation algorithms for prize collecting Steiner tree problems
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• 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
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• Near-optimal online algorithms for prize-collecting Steiner problems
• 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
• Approximation algorithm for stochastic prize-collecting Steiner tree problem
• 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
• New primal-dual algorithms for Steiner tree problems
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• A 4-approximation algorithm for k-prize collecting Steiner tree problems
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• scientific article; zbMATH DE number 1670544 (Why is no real title available?)

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)