In the Steiner Path Aggregation Problem , our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and k terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most 2 log 4 3 ⁡ k color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least log 2 ⁡ k color switches.

In the weighted minimum strongly connected spanning subgraph (WMSCSS ) problem we must purchase a minimum-cost strongly connected spanning subgraph of a digraph. We show that half-integral linear program (LP) solutions for WMSCSS can be efficiently rounded to integral solutions at a multiplicative 1.5 cost. This rounding matches a known 1.5 integrality gap lower bound for a half-integral instance. More generally, we show that LP solutions whose non-zero entries are at least a value f>0 can be rounded at a multiplicative cost of 2−f.

We show the reverse greedy algorithm is between a (2k−2)- and a 2k-approximation for k-center.