New primal-dual algorithms for Steiner tree problems

DOI10.1016/j.cor.2005.08.009zbMath1112.90070MaRDI QIDQ868154

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

integer programming; approximation algorithm; Steiner tree; primal-dual algorithm

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C46: Optimality conditions and duality in mathematical programming

90C27: Combinatorial optimization

68W20: Randomized algorithms

Related Items

A primal-dual approximation algorithm for the vertex cover \(P^3\) problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Primal-Dual-Based Algorithms for a Directed Network Design Problem
• A dual ascent approach for steiner tree problems on a directed graph
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Steiner problem in networks: A survey
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximation Algorithms for Directed Steiner Problems