About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1999
Conference paper
On the bidirected cut relaxation for the metric Steiner tree problem
Abstract
We give the first algorithmic result using the bidirected cut relaxation for the metric Steiner tree problem: a 3/2+ε factor approximation algorithm, for any ε>0, for the special case of quasi-bipartite graphs; these are graphs that do not have edges connecting pairs of Steiner vertices. This relaxation is conjectured to have integrality gap close to 1; the worst example known has integrality gap of 8/7. Our result places an upper bound of 3/2 on the integrality gap, for the special class of quasi-bipartite graphs. Part of the difficulty of designing an algorithm using the bidirected cut relaxation arises from edges connecting pairs of Steiner vertices. Restricting to quasi-bipartite graphs enables us to finesse this difficulty and address the rest of the aspects of the problem. The progress reported in this paper is quite similar to that made on the matching problem by restricting to bipartite graphs, thereby finessing the difficulty created by odd cycles.