Approximation of Steiner forest via the bidirected cut relaxation

DOI10.1007/S10878-019-00444-8zbMATH Open1433.90176arXiv1911.07234OpenAlexW3101152338WikidataQ127323108 ScholiaQ127323108MaRDI QIDQ2279758FDOQ2279758

Authors: Ali Çivril Edit this on Wikidata

Publication date: 13 December 2019

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Automata, Languages and Programming
• Approximation algorithms for Steiner forest: An experimental study

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)