All reports by Author Sanjeev Khanna:

__
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

__
TR06-109
| 29th August 2006
__

Julia Chuzhoy, Sanjeev Khanna#### Hardness of Directed Routing with Congestion

__
TR03-038
| 15th May 2003
__

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor#### Asymmetric k-center is log^*n-hard to Approximate

__
TR03-032
| 16th April 2003
__

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna#### Approximating Longest Directed Path

__
TR01-065
| 10th August 2001
__

Chandra Chekuri, Sanjeev Khanna#### Approximation Schemes for Preemptive Weighted Flow Time

__
TR00-073
| 28th August 2000
__

Venkatesan Guruswami, Sanjeev Khanna#### On the Hardness of 4-coloring a 3-colorable Graph

__
TR96-064
| 11th December 1996
__

Sanjeev Khanna, Madhu Sudan, Luca Trevisan#### Constraint satisfaction: The approximability of minimization problems.

__
TR96-062
| 3rd December 1996
__

Sanjeev Khanna, Madhu Sudan, David P. Williamson#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

__
TR96-028
| 9th April 1996
__

Sanjeev Khanna, Madhu Sudan#### The Optimization Complexity of Constraint Satisfaction Problems

__
TR95-023
| 16th May 1995
__

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani#### On Syntactic versus Computational views of Approximability

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

Julia Chuzhoy, Sanjeev Khanna

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

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

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

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

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

more >>>

Chandra Chekuri, Sanjeev Khanna

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

Venkatesan Guruswami, Sanjeev Khanna

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

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

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

Sanjeev Khanna, Madhu Sudan, David P. Williamson

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

Sanjeev Khanna, Madhu Sudan

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

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

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