New primal-dual algorithms for Steiner tree problems

DOI10.1016/J.COR.2005.08.009MaRDI QIDQ868154zbMATH OpenOpenAlexFDO

Authors Vardges Melkonian

Publication date 19 February 2007

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2005.08.009

zbMATH Keywords

approximation algorithminteger programmingprimal-dual algorithmSteiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Recommendations

• New approximation algorithms for the Steiner tree problems
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• New algorithms for Steiner tree reoptimization
• scientific article; zbMATH DE number 1670544
• scientific article; zbMATH DE number 139910
• A primal-dual approximation algorithm for the Steiner forest problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• New approximation algorithm for minimum Steiner tree problem
• scientific article; zbMATH DE number 4128830
• New reoptimization techniques applied to Steiner tree problem

Cites work

• scientific article; zbMATH DE number 1670544 (Why is no real title available?)
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 1305468 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Greedy Heuristic for the Set-Covering Problem
• A dual ascent approach for steiner tree problems on a directed graph
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for combinatorial problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On the ratio of optimal integral and fractional covers
• Primal-dual-based algorithms for a directed network design problem
• Steiner problem in networks: A survey
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(10)

• Subjectively interesting connecting trees and forests
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• A dual ascent approach for steiner tree problems on a directed graph
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• New reoptimization techniques applied to Steiner tree problem
• A practical greedy approximation for the directed Steiner tree problem
• Primal-dual-based algorithms for a directed network design problem
• The set covering problem revisited: an empirical study of the value of dual information
• A Lagrangean-based decomposition approach for the link constrained Steiner tree problem
• scientific article; zbMATH DE number 1670544 (Why is no real title available?)

This page was built for publication: New primal-dual algorithms for Steiner tree problems

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