An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem ∗ (2007)
Chandra Chekuri, Martin Pál, C. Chekuri, M. Pál
Abstract: We consider a variant of the traveling salesman problem (TSP): Given a directed graph G = (V,A) with non-negative arc lengths ℓ: A → R + and a pair of vertices s,t, find an s-t walk of...
On Average Throughput Benefits and Alphabet Size in Network Coding (2006)
Chekuri, C., Fragouli, C., Soljanin, E.
We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the...
On achievable information rates in single-source non-uniform demand networks (2006)
Chekuri, C., Fragouli, C., Soljanin, E.
A non-uniform demand network consists of a source and a set of receivers that have different min-cut values from the source. We look at the case where the receivers would like to receive from the...
On Average Throughput Benefits and Alphabet Size in Network Coding (2005)
Chekuri, C., Fragouli, C., Soljanin, E.
e analyze a special class of configurations with h sources and N receivers to demonstrate the throughput benefits of network coding and deterministic code design. We show that the throughput benefits...
The All-or-Nothing Multicommodity Flow Problem (2004)
m)), the same as that for edp [10]. Our algorithm extends to the case where each pair siti has a demand di associated with it and we need to completely route di to get credit for pair i. We also...
C. Chekuri, M. Mydlarz, F. B. Shepherd
Abstract We consider requests for capacity in a given tree network T = (V; E) where each edge of the tree has some integer capacity ue. Each request consists of an integer demand df and a profit wf...
Building Edge-Failure Resilient Networks (2002)
C. Chekuri, A. Gupta, A. Kumar, J. Naor, D. Raz
We consider the design of resilient networks that are fault tolerant against single link failures. Resilience against single link failures can be built into the network by providing backup paths,...
Building Edge-Failure Resilient Networks (2002)
C. Chekuri, A. Gupta, A. Kumar, J. Naor, D. Raz
We consider the design of resilient networks that are fault tolerant against link failures. Resilience against link failures can be built into the network by providing backup paths, which are used in...
Approximating a finite metric by a small number of tree metrics (1998)
M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin
Bartal [4, 5] gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O(log n log log n)....
Approximating a Finite Metric by a Small Number of Tree Metrics (1998)
M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin
Bartal [4, 5] gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O(logn log log n)....
Approximating a Finite Metric by a Small Number of Tree Metrics (1998)
Charikar Chekuri, M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin
Bartal [4, 5] gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O(logn log log n)....
Approximation Techniques for Average Completion Time Scheduling (1997)
C. Chekuri, R. Motwani, B. Natarajan, C. Stein
We consider the problem of non-preemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Approximation Techniques for Average Completion Time Scheduling (1997)
Chekuri Stanford, C. Chekuri, R. Motwani, B. Natarajan, Hewlett Packard Laboratories, C. Stein
We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Approximation Techniques for Average Completion Time Scheduling (1997)
Chekuri Motwani Natarajan, C. Chekuri, R. Motwani, B. Natarajan, C. Stein
We consider the problem of non-preemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Approximation Techniques for Average Completion Time Scheduling (1997)
C. Chekuri, R. Motwani, B. Natarajan, Hewlett Packard Laboratories, C. Stein
We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Approximation Techniques for Average Completion Time Scheduling (1997)
C. Chekuri, R. Motwani, B. Natarajan, Hewlett Packard Laboratories, C. Stein
We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Approximation Techniques for Average Completion Time Scheduling (1997)
Chekuri Stanford, C. Chekuri, R. Motwani, B. Natarajan, Hewlett Packard Laboratories, C. Stein
We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to...
Profile-Driven Instruction Level Parallel Scheduling with Application to Super Blocks (1996)
Chekuri Dept, C. Chekuri, R. Johnson, Hewlett Packard Labs, R. Motwani, B. Natarajan
Code scheduling to exploit instruction level parallelism (ILP) is a critical problem in compiler optimization research, in light of the increased use of long-instructionword machines. Unfortunately,...
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) (1996)
D. Aingworth, C. Chekuri, R. Motwani
this paper is organized as follows. We begin by presenting some definitions and useful observations in Section 2. In Section 3, we describe the algorithms for distinguishing between graphs of...
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) (1996)
D. Aingworth, C. Chekuri, P. Indyk, R. Motwani
In the recent past, there has been considerable progress in devising algorithms for the allpairs shortest paths problem running in time significantly smaller than the obvious time bound of O(n 3 )....
Profile-Driven Instruction Level Parallel Scheduling with Application to Super Blocks (1996)
Chekuri Dept Of, C. Chekuri, R. Johnson, Hewlett Packard Labs, R. Motwani, B. Natarajan
Code scheduling to exploit instruction level parallelism (ILP) is a critical problem in compiler optimization research, in light of the increased use of long-instructionword machines. Unfortunately,...
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) (1996)
D. Aingworth, C. Chekuri, P. Indyk, R. Motwani
In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths problem running in time significantly smaller than the obvious time bound of...
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) (1996)
D. Aingworth, C. Chekuri, R. Motwani
this paper, we will working with a parameter s to be chosen later that will serve as the threshold for classifying vertices as being of low degree or high degree. This threshold is implicit in the...