MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

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 >>>

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

In the undirected Edge-Disjoint Paths problem with Congestion

(EDPwC), we are given an undirected graph with $V$ nodes, a set of

terminal pairs and an integer $c$. The objective is to route as many

terminal pairs as possible, subject to the constraint that at most

$c$ demands can be routed ...
more >>>