Approximation of Steiner forest via the bidirected cut relaxation

DOI10.1007/S10878-019-00444-8MaRDI QIDQ2279758zbMATH OpenOpenAlexWikidataFDO

Authors Ali Çivril

Publication date 13 December 2019

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.07234

zbMATH Keywords

combinatorial optimizationapproximation algorithmsSteiner forestbidirected cut relaxationprimal-dual schema

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: The classical algorithm of Agrawal, Klein and Ravi [SIAM J. Comput., 24 (1995), pp. 440-456], stated in the setting of the primal-dual schema by Goemans and Williamson [SIAM J. Comput., 24 (1995), pp. 296-317] uses the undirected cut relaxation for the Steiner forest problem. Its approximation ratio is $2-frac1k$, where $k$ is the number of terminal pairs. A variant of this algorithm more recently proposed by K"onemann et al. [SIAM J. Comput., 37 (2008), pp. 1319-1341] is based on the lifted cut relaxation. In this paper, we continue this line of work and consider the bidirected cut relaxation for the Steiner forest problem, which lends itself to a novel algorithmic idea yielding the same approximation ratio as the classical algorithm. In doing so, we introduce an extension of the primal-dual schema in which we run two different phases to satisfy connectivity requirements in both directions. This reveals more about the combinatorial structure of the problem. In particular, there are examples on which the classical algorithm fails to give a good approximation, but the new algorithm finds a near-optimal solution.

Recommendations

• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem
• A primal-dual approximation algorithm for the Steiner forest problem
• scientific article; zbMATH DE number 1305468
• A partition-based relaxation for Steiner trees

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• A catalog of steiner tree formulations
• A local-search algorithm for Steiner forest
• A primal-dual approximation algorithm for generalized Steiner network problems
• Greedy algorithms for Steiner forest
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The design of approximation algorithms
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(3)

• Approximation algorithms for Steiner forest: An experimental study
• scientific article; zbMATH DE number 1305468 (Why is no real title available?)
• Automata, Languages and Programming

This page was built for publication: Approximation of Steiner forest via the bidirected cut relaxation

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