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

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

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

We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on $n$ vertices. We show that neither of these two problems can be polynomial time approximated within $n^{1-\epsilon}$ for any $\epsilon>0$ unless $\text{P}=\text{NP}$. In particular, the result holds for digraphs of constant bounded outdegree ... more >>>

We present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a $(1+\eps)$-approximate solution for any instance of weighted flow time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio of maximum job processing ... more >>>

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This highlights a ... more >>>

This paper continues the work initiated by Creignou [Cre95] and Khanna, Sudan and Williamson [KSW96] who classify maximization problems derived from boolean constraint satisfaction. Here we study the approximability of {\em minimization} problems derived thence. A problem in this framework is characterized by a collection F of "constraints" (i.e., functions ... more >>>

In this paper we study the approximability of boolean constraint satisfaction problems. A problem in this class consists of some collection of ``constraints'' (i.e., functions $f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set of constraints applied to specified subsets of $n$ boolean variables. Schaefer earlier studied the ... more >>>

In 1978, Schaefer considered a subclass of languages in NP and proved a ``dichotomy theorem'' for this class. The subclass considered were problems expressible as ``constraint satisfaction problems'', and the ``dichotomy theorem'' showed that every language in this class is either in P, or is NP-hard. This result is in ... more >>>

We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP allow for clean complexity-theoretic results and natural complete problems, while computational classes such as APX allow us to work with problems whose approximability is well-understood. Our results give a computational ... more >>>