Search

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

Abstract: The set cover problem is that of computing a minimum weight subfamily , given a family of weighted subsets of a base set U, such that every element of U is covered by some subset in . The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai–Edmonds structure theorem for maximum matchings. [Copyright &y& Elsevier]