  The Steiner Multicycle problem consists of, given a complete graph, a weight
function on its vertices, and a collection of pairwise disjoint non-unitary
sets called terminal sets, finding a minimum weight collection of
vertex-disjoint cycles in the graph such that, for every terminal set, all of
its vertices are in a same cycle of the collection. This problem generalizes
the Traveling Salesman problem and therefore is hard to approximate in general.
On the practical side, it models a collaborative less-than-truckload problem
with pickup and delivery locations. Using an algorithm for the Survivable
Network Design problem and T -joins, we obtain a 3-approximation for the metric
case, improving on the previous best 4-approximation. Furthermore, we present
an (11/9)-approximation for the particular case of the Steiner Multicycle in
which each edge weight is 1 or 2. This algorithm can be adapted to obtain a
(7/6)-approximation when every terminal set contains at least 4 vertices.
Finally, we devise an O(lg n)-approximation algorithm for the asymmetric
version of the problem.
