Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NETWORK DESIGN:
Reports tagged with network design:
TR06-007 | 23rd November 2005
MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

#### Approximating Buy-at-Bulk $k$-Steiner trees

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 >>> TR06-008 | 23rd November 2005 MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour #### Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk 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 >>>

ISSN 1433-8092 | Imprint