Chandra Chekuri's Publications

Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

I have classified my papers into broad categories and placed each of them in what in my opinion is the most appropriate category. If a paper is listed here but is not available for download, it is for a good reason - it is not yet ready for public distribution. I will put it up as soon as it is ready.

Recent Publications

  • Min-Cost 2-Connected Subgraphs with k Terminals
    (with Nitish Korula).
    Manuscript, 2007.

  • Algorithms for 2-Route Cut Problems
    (with Sanjeev Khanna).
    ICALP 2008. To appear. A longer version with proofs.

  • Approximation Algorithms for Orienteering with Timewindows
    (with Nitish Korula).
    Manuscript, September 2007.

  • Set Connectivity Problems in Undirected Graphs and the Directed Steiner Network Problem
    (with Guy Even, Anupam Gupta, and Danny Segev).
    SODA 2008.

  • Routing and Network Design with Robustness to Changing or Uncertain Traffic Demands
    A survey in SIGACT News, 38(3): 106--128, September 2007.

  • Improved Algorithms for Orienteering and Related Problems
    (with Nitish Korula and Martin Pal).
    SODA 2008.

  • Buy-at-Bulk Network Design with Protection
    (with Spyros Antonakapoulos, Bruce Shepherd and Lisa Zhang).
    FOCS 2007.

  • Disjoint Bases in a Polymatroid
    (with Gruia Calinescu and Jan Vondrak).
    Manuscript, February 2007. Submitted.

  • Maximizing a Submodular Set Function subject to a Matroid Constraint
    (with Gruia Calinescu, Martin Pal and Jan Vondrak).
    IPCO 2007.

  • Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    SODA 2007.

  • Approximation Algorithms for Non-uniform Buy-at-Bulk Network Design Problems
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    FOCS 2006.

  • On Achievable Information Rates in Single-Source Non-Uniform Demand Networks
    (with Christina Fragouli and Emina Soljanin).
    ISIT, 2006.

  • Non-Cooperative Multicast and Facility Location Games
    (with Julia Chuzoy, Liane Lewin-Eytan, Seffi Naor and Ariel Orda).
    EC, 2006.

  • A Note on Multiflows and Treewidth
    (with Sanjeev Khanna and Bruce Shepherd).
    Algorithmica.

  • An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
    (with Martin Pál).
    Theory of Computing, Vol 3, 197--209, 2007. Preliminary version in APPROX 2006.
    See also a relevant comment on the paper by Viswanath Nagarajan.

  • Edge-Disjoint Paths in Planar Graphs with Constant Congestion
    (with Sanjeev Khanna and Bruce Shepherd).
    Submitted to SICOMP special issue for STOC, 2006. Conference version.

  • An O(\sqrt{n}) Approximation and Integrality Gap for Disjoint Paths and UFP
    (with Sanjeev Khanna and Bruce Shepherd).
    Theory of Computing, Vol 2, 137--146, 2006.

    • Approximation Algorithms and Combinatorial Optimization

  • Min-Cost 2-Connected Subgraphs with k Terminals
    (with Nitish Korula).
    Manuscript, 2007.

  • Algorithms for 2-Route Cut Problems
    (with Sanjeev Khanna).
    ICALP 2008. To appear. A longer version with proofs.

  • Approximation Algorithms for Orienteering with Timewindows
    (with Nitish Korula).
    Manuscript, September 2007.

  • Set Connectivity Problems in Undirected Graphs and the Directed Steiner Network Problem
    (with Guy Even, Anupam Gupta, and Danny Segev).
    SODA 2008.

  • Improved Algorithms for Orienteering and Related Problems
    (with Nitish Korula and Martin Pal).
    SODA 2008.

  • Routing and Network Design with Robustness to Changing or Uncertain Traffic Demands
    A survey in SIGACT News, 38(3): 106--128, September 2007.

  • Buy-at-Bulk Network Design with Protection
    (with Spyros Antonakapoulos, Bruce Shepherd and Lisa Zhang).
    FOCS 2007.

  • Disjoint Bases in a Polymatroid
    (with Gruia Calinescu and Jan Vondrak).
    Manuscript, February 2007. Submitted.

    • Maximizing a Submodular Set Function subject to a Matroid Constraint
    (with Gruia Calinescu, Martin Pal and Jan Vondrak).
    IPCO 2007.

  • Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    SODA 2007.

  • Approximation Algorithms for Non-uniform Buy-at-Bulk Network Design Problems
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    FOCS 2006.

  • A Note on Multiflows and Treewidth
    (with Sanjeev Khanna and Bruce Shepherd).
    To appear in Algorithmica.

  • An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
    (with Martin Pál).
    Theory of Computing, Vol 3, 197--209, 2007. Preliminary version in APPROX 2006.
    See also a relevant comment on the paper by Viswanath Nagarajan.

  • Edge-Disjoint Paths in Planar Graphs with Constant Congestion
    (with Sanjeev Khanna and Bruce Shepherd).
    Submitted to SICOMP special issue for STOC, 2006. Conference version.

  • An O(\sqrt{n}) Approximation and Integrality Gap for Disjoint Paths and UFP
    (with Sanjeev Khanna and Bruce Shepherd).
    Theory of Computing, Vol 2, 137--146, 2006.

  • A Recursive Greedy Algorithm for Walks in Directed Graphs
    (with Martin Pál).
    FOCS, 2005.

  • Sampling Bounds for Stochastic Optimization
    (with Moses Charikar and Martin Pál).
    RANDOM, 2005.

  • Multicommodity flow, well-linked terminals, and routing problems
    (with Sanjeev Khanna and Bruce Shepherd).
    STOC, 2005.
    Note: The results in this paper for node capacitated problems have been improved to match those for the edge capacitated problems. A paper on this will be posted in the near future.

  • Hardness of Robust Network Design
    (with Gianpaolo Oriolo, Maria Scutella, and Bruce Shepherd).
    Networks, 50(1):50--54, 2007. Preliminary version in INOC 2005.

  • Approximate Integer Decompositions for Undirected Network Design Problems
    (with Bruce Shepherd).
    Manuscript, October 2004. Submitted.

  • Edge Disjoint Paths in Planar Graphs
    (with Sanjeev Khanna and Bruce Shepherd).
    FOCS, 2004.

  • The All-or-Nothing Multicommodity Flow Problem
    (with Sanjeev Khanna and Bruce Shepherd).
    STOC,  2004. Slides of talk at STOC.
    Note: The algorithm in the paper to achieve congestion 1 is not kosher. A corrected draft will be posted eventually. Send email if you are in a hurry.

  • Maximum Coverage Problem with Group Budget Consrtaints and Applications
    (with Amit Kumar).
    APPROX, 2004.

  • On a Bidirected Relaxation for the Multiway Cut Problem
    (with Anupam Gupta and Amit Kumar).
    Discrete Applied Mathematics, 150:(1-3), 67-79, 2005.

  • Multicommodity Demand Flow in a Tree and Packing Integer Programs
    (with Marcelo Mydlarz and Bruce Shepherd).
    ACM Transactions on Algorithms (TALG), 3(3), 2007. Preliminary version appeared in ICALP 2003.

  • Approximating Steiner k-Cuts
    (with Sudipto Guha and Seffi Naor).
    SIAM J. on Discrete Math, 20(1):261--271, 2006. Preliminary version that appeared in ICALP 2003 is buggy.

  • A greedy approximation algorithm for the group Steiner problem
    (with two guys, Guy Even and Guy Kortsarz).
    Discrete Applied Mathematics, 154(1):15--34, 2006.

  • Embedding k-Outerplanar Graphs into l1
    (with Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair).
    SIAM Journal on Discrete Math, 20(1):119--136, 2006. Preliminary version in ACM-SIAM SODA, January 2003.

  • Edge Disjoint Paths Revisited
    (with Sanjeev Khanna).
    ACM Transactions on Algorithms (TALG), 4(3), November 2007. Preliminary version in SODA, January 2003.

  • Approximation Algorithms for the Unsplittable Flow Problem
    (with Amit Chakrabarti, Amit Kumar, and Anupam Gupta).
    Algorithmica, 47(1):53--78, 2007. Preliminary version in APPROX, September 2002.

  • Building Edge-Failure Resilient Networks
    (with Amit Kumar, Anupam Gupta, Seffi Naor, and Danny Raz).
    Algorithmica, 43(1-2):17-41, 2005. Preliminary version in IPCO, May 2002.

  • A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
    (with Sanjeev Khanna, Seffi Naor, and Lenoid Zosin).
    SIAM J. on Discrete Mathematics, 18(3):606-635, 2005. Preliminary version in 12th SODA, January 2001.

  • A Deterministic Algorithm for the Cost-Distance Problem
    (with Sanjeev Khanna and Seffi Naor).
    Two page short paper in SODA, January 2001.

  • A PTAS for the Multiple Knapsack Problem
    (with Sanjeev Khanna).
    SIAM Journal on Computing, 35(3):713--728, 2006.
    Preliminary version in 11th SODA, January 2000.

  • Performance Guarantees for the TSP with a Parameterized Triangle Inequality
    (with Michael Bender).
    Information Processing Letters, 73:(1-2), 17-21, January 2000. 

  • On Multi-dimensional Packing Problems
    (with Sanjeev Khanna).
    SIAM Journal on Computing, 33(4):837--851, 2004.
    Preliminary version 10th SODA, January 1999.

  • Approximating a Finite Metric by a Small Number of Tree Metrics
    (with Moses Charikar, Ashish Goel, Sudipto Guha, and Serge Plotkin).
    39th FOCS, November 1998.

  • Rounding via trees: deterministic approximation algorithms for group Steiner trees and $k$ median
    (with Moses Charikar, Ashish Goel, and Sudipto Guha)
    30th STOC, May 1998.

  • Approximation Algorithms for Directed Steiner Problems
    (with Moses Charikar, Toyat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li)
    in Journal of Algorithms, 1999, 33: 73-91.
    Preliminary version in 9th SODA, January 1998.
    Note: For the directed Steiner tree problem, the paper claims an O(log^2 k) approximation. This is based on an incorrect lemma of Zelikovsky on the height reduction of trees. Using a corrected lemma the ratio that can be obtained is O(log^3 k).

    • Scheduling Theory

  • Multi-processor Scheduling to Minimize Flowtime with eps Resource Augmentation
    (with Ashish Goel, Sanjeev Khanna and Amit Kumar).
    STOC, June 2004.

  • Approximation Algorithms for Minimizing Average Weighted Completion Time
    (with Sanjeev Khanna).
    September 2003. Chapter in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, edited by Joseph Leung, CRC Press, 2004.

  • Approximation Schemes for Preemptive Weighted Flow Time
    (with Sanjeev Khanna).
    34th STOC, May 2002.
    Preliminary version as ECCC Report TR01-065, September 2001.

  • Algorithms for Minimizing Weighted Flow Time
    (with Sanjeev Khanna and An Zhu)
    33rd STOC, July 2001.

  • A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
    (with Sanjeev Khanna)
    28th ICALP, July 2001.

  • Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
    (with F. Afrati, E. Bampis, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko)
    40th FOCS, October 1999.

  • My PhD Thesis: Approximation Algorithms for Scheduling Problems
    Technical Report CS-TR-98-1611, Computer Science Department, Stanford University. August 1998.

  • Efficient approximation algorithm for minimizing makespan on uniformly related machines
    (with Michael Bender)
    Journal of Algorithms, 41(2):212--224, 2001.
    Preliminary version in IPCO, June 1998.

  • Precedence Constrained Scheduling to Minimize Weighted Completion Time on a Single Machine
    (with Rajeev Motwani)
    Discrete Applied Mathematics, 98:(1-2), 29-38, November 1999.
    A preliminary version of this appeared as a two page short paper in SODA 1999.

  • Approximation Techniques for Average Completion Time Scheduling  
    (with Rajeev Motwani, Balas Natarajan, and Cliff Stein)
    SIAM Journal on Computing, 31(1):146--166, 2000.
    Preliminary version in 8th SODA, 1997.

  • An Analysis of Profile-Driven Instruction Level Parallel Scheduling with Application to Super Blocks
    (with Richard Johnson, Rajeev Motwani, Balas Natarajan, Bob Rau, and Michael Schlansker)
    MICRO-29, December 1996.

  • Scheduling Problems in Parallel Query Optimization
    (with Waqar Hasan and Rajeev Motwani)
    14th PODS, 1995.

    • Graph Problems

  • Experimental Study of Minimum Cut Algorithms
    (with Andrew Goldberg, David Karger, Matthew Levine, and Cliff Stein)
    8th SODA, 1997.
    You can also get a full version of the paper and the code we developed.

  • Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)
    (with Donald Aingworth, Piotr Indyk, and Rajeev Motwani)
    SIAM Journal on Computing, 1999, 28(2):1167-1181.
    Preliminary version (with Donald Aingworth and Rajeev Motwani)
    7th SODA, 1996, pp. 547-553.

    • Information Retrieval

  • Incremental Clustering and Dynamic Information Retrieval
    (with Moses Charikar, Tomas Feder, and Rajeev Motwani)
    SIAM Journal on Computing, 33(6):1417--1440, 2004.
    Preliminary version in 29th STOC, 1997.

  • Web Search Using Automated Classification
    (with Michael Goldwasser, Prabhakar Raghavan, and Eli Upfal)
    Poster at WWW6, 1997.

    • Databases

  • Filtering with approximate predicates
    (with Narayanan Shivakumar and Hector Garcia-Molina)
    VLDB , New York, August 1998.

  • Conjunctive Query Containment Revisited
    (with Anand Rajaraman)
    Theoretical Computer Science, 239(2), 2000.
    Preliminary version 6th ICDT, 1997. Best Student Paper Award.

    • Miscellaneous

  • Non-Cooperative Multicast and Facility Location Games
    (with Julia Chuzoy, Liane Lewin-Eytan, Seffi Naor and Ariel Orda).
    EC, 2006.

  • On Achievable Information Rates in Single-Source Non-Uniform Demand Networks
    (with Christina Fragouli and Emina Soljanin).
    ISIT, 2006.

  • On Average Throughput and Alphabet Size in Network Coding
    (with Christina Fragouli and Emina Soljanin).
    IEEE Transactions on Information Theory, 52(6):2410 - 2424, 2006.

  • DCM Selection for an Optical Line System.
    (with Wonsuck Lee and Lisa Zhang).
    Networks 2004.

  • Optical Line System Configuration via Dynamic Programming.
    (with Wonsuck Lee and Lisa Zhang).
    International Network Optimization Conference (INOC),  October 2003.

  • Blocking Probability Estimates in a Partitioned Sector TDMA System
    (with Kavita Ramanan, Phil Whiting, and Lisa Zhang).
    4th Dial M for Mobility, August 2000.

    • Back to Chandra's home page.