Approximation of Steiner forest via the bidirected cut relaxation

Ali Çivril ()

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 13, 1196-1212

Abstract: Abstract The classical algorithm of Agrawal et al. (SIAM J Comput 24(3):440–456, 1995), stated in the setting of the primal-dual schema by Goemans and Williamson (SIAM J Comput 24(2):296–317, 1995) uses the undirected cut relaxation for the Steiner forest problem. Its approximation ratio is $$2-\frac{1}{k}$$ 2 - 1 k , where k is the number of terminal pairs. A variant of this algorithm more recently proposed by Könemann et al. (SIAM J Comput 37(5):1319–1341, 2008) 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.

Keywords: Steiner forest; Bidirected cut relaxation; Primal-dual schema; Approximation algorithms; Combinatorial optimization (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00444-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00444-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00444-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().