Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Multicommodity flow:
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 >>>

TR07-113 | 15th November 2007
Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

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

ISSN 1433-8092 | Imprint