Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Julia Chuzhoy:

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

TR06-109 | 29th August 2006
Julia Chuzhoy, Sanjeev Khanna

Hardness of Directed Routing with Congestion

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

TR03-038 | 15th May 2003
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

Asymmetric k-center is log^*n-hard to Approximate

We show that the asymmetric $k$-center problem is
$\Omega(\log^* n)$-hard to approximate unless
${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.
Since an $O(\log^* n)$-approximation algorithm is known
for this problem, this essentially resolves the approximability
of this problem. This is the first natural problem
whose approximability threshold does not polynomially ... more >>>

ISSN 1433-8092 | Imprint