Approximation algorithms for Steiner forest: An experimental study

DOI10.1002/NET.22046MaRDI QIDQ6065858zbMATH OpenOpenAlexFDO

Authors Laleh Ghalami, D. Grosu

Publication date 11 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.22046

zbMATH Keywords

approximation algorithmsperformance evaluationSteiner forest

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming (90-10) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• Greedy algorithms for Steiner forest
• A primal-dual approximation algorithm for the Steiner forest problem
• Strong Steiner tree approximations in practice
• An approximation algorithm to the \(k\)-Steiner forest problem
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• A local-search algorithm for Steiner forest
• A tight bound on approximating arbitrary metrics by tree metrics
• An algorithm for the steiner problem in graphs
• An integer linear programming approach to the steiner problem in graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation of Steiner forest via the bidirected cut relaxation
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Designing network protocols for good equilibria
• Fast local search for Steiner trees in graphs
• Greedy algorithms for Steiner forest
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1926656 (Why is no real title available?)
• Improved algorithms for the Steiner problem in networks
• On approximating planar metrics by tree metrics.
• On Steiner’s Problem with Rectilinear Distance
• Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
• Reducibility among combinatorial problems
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Strong formulations for network design problems with connectivity requirements
• Strong Steiner tree approximations in practice
• The design of approximation algorithms
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(2)

• Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

This page was built for publication: Approximation algorithms for Steiner forest: An experimental study

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