We consider the k-Directed Steiner Forest} (k-dsf) problem: given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs ... more >>>

We consider the non-uniform multicommodity buy-at-bulk network design problem. In this problem we are given a graph $G(V,E)$ with two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost $r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$) with each pair $i$ ... more >>>

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy $k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set of terminals $T\subseteq V$ including a particular vertex $s$ called the root, and an integer $k\leq |T|$. There are two cost functions on the edges of $G$, a buy cost $b:E\longrightarrow ... more >>>

In the {\sc $k$-center} problem, the input is a bound $k$ and $n$ points with the distance between every two of them, such that the distances obey the triangle inequality. The goal is to choose a set of $k$ points to serve as centers, so that the maximum distance from ... more >>>