Chandra Chekuri's Papers


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 Papers

  • Centrality of Trees for Capacitated k-Center
    (with Hyung-Chan An, Aditya Bhaskara, Shalmoli Gupta, Vivek Madan and Ola Svensson).
    Extended abstract in IPCO 2014.
    Note: The main result in this paper was obtained independently by two groups: An, Bhaskara and Svensson, and the rest of us at UIUC.
  • Polynomial Bounds for the Grid-Minor Theorem
    (with Julia Chuzhoy).
    Manuscript, May 2013, updated October 2013. Extended abstract to appear in STOC 2014
  • The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    (with Alina Ene).
    Manuscript, April 2013. Extended abstract in IPCO 2014.
  • Approximation algorithms for Euler genus and related problems
    (with Anastasios (Tasos) Sidiropoulos).
    Extended abstract in FOCS 2013.
  • Maximum Edge Disjoint Paths in k-Sums of Graphs
    (with Guyslain Naves and Bruce Shepherd).
    Extended abstract in ICALP 2013.
  • Large-Treewidth Graph Decompositions and Applications
    (with Julia Chuzhoy).
    Extended abstract in STOC 2013.
  • Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
    (with Alina Ene).
    SODA 2013.
  • Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
    (with Sungjin Im and Ben Moseley).
    Theory of Computing, Vol 8, 165-195, 2012. Special issue in honor of my late advisor Rajeev Motwani.
    Combines and extends results from a SODA 2009 paper and an ESA 2009 paper.
  • Prize-collecting Survivable Network Design in Node-weighted Graphs
    (with Alina Ene and Ali Vakilian).
    APPROX 2012.
    Note: A longer version will be posted to the ArXiv in the near(?) future.
  • Maximum Throughput Multicommodity Flow vs Multicut in Planar and $K_h$-minor-free Polymatroidal Networks
    (with Sreeram Kannan and Pramod Viswanath).
    Manuscript, April 2012.
  • Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    (with Alina Ene and Ali Vakilian).
    ICALP 2012.
    Note: A longer version with some claimed extensions will be posted to the ArXiv, hopefully soon.
  • Multicommodity Flows and Cuts in Polymatroidal Networks
    (with Sreeram Kannan, Adnan Raja and Pramod Viswanath).
    ArXiv, Oct 2011. Extended abstract to appear in ITCS (Innovations in TCS) 2012.
  • Approximation Algorithms for Submodular Multiway Partition
    (with Alina Ene).
    FOCS 2011.
    Preliminary version, ArXiv, May 2011.
  • Submodular Cost Allocation Problem and Applications
    (with Alina Ene).
    ArXiv, May 2011. Extended abstract in ICALP 2011.
  • Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
    (with Jan Vondrak and Rico Zenklusen).
    To appear in SICOMP.
    Shorter version in STOC 2011.
  • Approximability of Capacitated Network Design
    (with Deeparnab Chakrabarty, Sanjeev Khanna and Nitish Korula).
    Manuscript, November 2009. ArXiv, September 2010. IPCO, 2011.
  • Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
    (with Jan Vondrak and Rico Zenklusen).
    SODA 2011.
  • Prize-Collecting Steiner Tree and Forest in Planar Graphs
    (with Alina Ene and Nitish Korula).
    ArXiv, June 2010.
    Note: Results merged with those in an independent paper by Bateni, Hajiaghayi and Marx and the combined paper is in SODA 2011.
  • Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
    (with Jan Vondrak and Rico Zenklusen).
    FOCS 2010.
    Note: Longer version with proofs and details will be posted in the future. An earlier version of the paper Dependent Randomized Rounding for Matroid Polytopes and Applications
  • New Models and Algorithms for Throughput Maximization in Broadcast Schedulng
    (with Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Ben Moselely, and Louiqa Raschid).
    WAOA 2010.
  • Improved Algorithms for Orienteering and Related Problems
    (with Nitish Korula and Martin Pal).
    ACM Transactions on Algorithms (TALG), Vol 8, Issue 3, July 2012.
    Note: This journal paper contains results from a SODA 2008 paper with the same title and authors, and an unpublished manuscript with Nitish Korula on orienteering with time windows.
  • Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    SICOMP, 39(5):1772--1798, 2009.
    Note: This journal paper combines results from two papers on buy-at-bulk network design that appeared in FOCS 2006 and SODA 2007 .
  • Flow-Cut Gaps for Integer and Fractional Multiflows
    (with Bruce Shepherd and Christophe Weibel).
    J. of Combinatorial Theory, Ser B, published online, Dec 2012.
    Preliminary version in SODA 2010.
  • Approximation Algorithms and Combinatorial Optimization

  • Centrality of Trees for Capacitated k-Center
    (with Hyung-Chan An, Aditya Bhaskara, Shalmoli Gupta, Vivek Madan and Ola Svensson).
    Extended abstract in IPCO 2014.
    Note: The main result in this paper was obtained independently by two groups: An, Bhaskara and Svensson, and the rest of us at UIUC.
  • Polynomial Bounds for the Grid-Minor Theorem
    (with Julia Chuzhoy).
    Manuscript, May 2013, updated October 2013. Extended abstract to appear in STOC 2014.
  • The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    (with Alina Ene).
    Manuscript, April 2013. Extended abstract in IPCO 2014.
  • Approximation algorithms for Euler genus and related problems
    (with Anastasios (Tasos) Sidiropoulos).
    Extended abstract in FOCS 2013.
  • Maximum Edge Disjoint Paths in k-Sums of Graphs
    (with Guyslain Naves and Bruce Shepherd).
    Extended abstract in ICALP 2013.
  • Large-Treewidth Graph Decompositions and Applications
    (with Julia Chuzhoy).
    Extended abstract in STOC 2013.
  • Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion
    (with Alina Ene).
    SODA 2013.
  • Prize-collecting Survivable Network Design in Node-weighted Graphs
    (with Alina Ene and Ali Vakilian).
    APPROX 2012.
    Note: A longer version will be posted to the ArXiv in the near(?) future.
  • Maximum Throughput Multicommodity Flow vs Multicut in Planar and $K_h$-minor-free Polymatroidal Networks
    (with Sreeram Kannan and Pramod Viswanath).
    Manuscript, April 2012.
  • Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    (with Alina Ene and Ali Vakilian).
    ICALP 2012.
    Note: A longer version with some claimed extensions will be posted to the ArXiv, hopefully soon.
  • Multicommodity Flows and Cuts in Polymatroidal Networks
    (with Sreeram Kannan, Adnan Raja and Pramod Viswanath).
    ArXiv, Oct 2011. Extended abstract to appear in ITCS (Innovations in TCS) 2012.
  • Approximation Algorithms for Submodular Multiway Partition
    (with Alina Ene).
    FOCS 2011.
    Preliminary version, ArXiv, May 2011.
  • Submodular Cost Allocation Problem and Applications
    (with Alina Ene).
    ArXiv, May 2011. Extended abstract in ICALP 2011.
  • Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
    (with Jan Vondrak and Rico Zenklusen).
    To appear in SICOMP.
    Shorter version in STOC 2011.
  • Approximability of Capacitated Network Design
    (with Deeparnab Chakrabarty, Sanjeev Khanna and Nitish Korula).
    Manuscript, November 2009. ArXiv, September 2010. IPCO, 2011.
  • Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
    (with Jan Vondrak and Rico Zenklusen).
    SODA 2011.
  • Prize-Collecting Steiner Tree and Forest in Planar Graphs
    (with Alina Ene and Nitish Korula).
    ArXiv, June 2010.
    Note: Results merged with those in an independent paper by Bateni, Hajiaghayi and Marx and the combined paper is in SODA 2011.
  • Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
    (with Jan Vondrak and Rico Zenklusen).
    FOCS 2010.
    Note: Longer version with proofs and details will be posted in the future. An earlier version of the paper Dependent Randomized Rounding for Matroid Polytopes and Applications
  • Improved Algorithms for Orienteering and Related Problems
    (with Nitish Korula and Martin Pal).
    ACM Transactions on Algorithms (TALG), Vol 8, Issue 3, July 2012.
    Note: This journal paper contains results from a SODA 2008 paper with the same title and authors, and an unpublished manuscript with Nitish Korula on orienteering with time windows.
  • Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design
    (with MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour).
    SICOMP, 39(5):1772--1798, 2009.
    Note: This journal paper combines results from two papers on buy-at-bulk network design that appeared in FOCS 2006 and SODA 2007 .
  • Flow-Cut Gaps for Integer and Fractional Multiflows
    (with Bruce Shepherd and Christophe Weibel).
    J. of Combinatorial Theory, Ser B, published online, Dec 2012.
    Preliminary version in SODA 2010.
  • UFP in Paths and Trees and Column-Restricted Packing Integer Programs
    (with Alina Ene and Nitish Korula).
    APPROX 2009.
    Note: The above link is to a longer version that has new results/observations that were not in the conference version.
  • Truthful Mechansims via Greedy Iterative Packing
    (with Iftah Gamzu).
    APPROX 2009.
  • A Graph Reduction Step Preserving Element-Connectivity and Applications
    (with Nitish Korula).
    ICALP 2009.
  • On the Set Multi-Cover Problem in Geometric Settings
    (with Ken Clarkson and Sariel Har-Peled).
    ACM Transactions on Algorithms (TALG), 9(1), 2012.
    Preliminary version in ACM SoCG 2009.
  • Maximizing a Monotone Submodular Function subject to a Matroid Constraint
    (with Gruia Calinescu, Martin Pal and Jan Vondrak).
    SICOMP 40:6 (2011), special section on STOC 2008, 1740-1766.
    Note: This paper combines our IPCO 2007 paper with essentially the same title (see below) and a beautiful follow up paper of Jan Vondrak (appeared in STOC 2008) that closed the problem. Jan generously insisted that we write a combined journal version.
  • Single-sink Network Design with Vertex Connectivity Requirements
    (with Nitish Korula).
    Manuscript, April 2008. FSTTCS, December 2008. Longer version with proofs coming soon.
  • Pruning 2-Connected Graphs
    (with Nitish Korula).
    Algorithmica, published online November 2010. Short version in FSTTCS, December 2008.
    Preliminary version with a different title in ArXiv.
  • Algorithms for 2-Route Cut Problems
    (with Sanjeev Khanna).
    ICALP 2008. 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).
    ACM Transactions on Algorithms (TALG), Vol 7, No 2, March 2011. Preliminary version in 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).
    Math. of OR, 36(1): 71--87, 2011. Preliminary version in FOCS 2007.
  • Disjoint Bases in a Polymatroid
    (with Gruia Calinescu and Jan Vondrak).
    Random Structures & Algorithms, 35(4): 418-430, 2009.
  • 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).
    Algorithmica, 53(3): 400-412, July 2009. Manuscript, 2006 and published online 2007.
  • 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 comment on the paper by Viswanath Nagarajan.

  • Edge-Disjoint Paths in Planar Graphs with Constant Congestion
    (with Sanjeev Khanna and Bruce Shepherd).
    SIAM J. on Computing 39(1): 281-301, 2009. 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).
    SIAM J. on Discrete Math, 23(1):163--177, 2008.
  • 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).
    Preliminary version in STOC,  2004. Slides of talk at STOC.
    Note: The journal version posted here fixes some bugs in the STOC version.
  • Maximum Coverage Problem with Group Budget Constraints 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

  • Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
    (with Sungjin Im and Ben Moseley).
    Theory of Computing, Vol 8, 165-195, 2012. Special issue in honor of my late advisor Rajeev Motwani.
    Combines and extends results from a SODA 2009 paper and an ESA 2009 paper.
  • New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
    (with Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Ben Moselely, and Louiqa Raschid).
    WAOA 2010.
  • Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
    (with Sungjin Im and Ben Moseley).
    ESA 2009.
  • Longest Wait First and Broadcast Scheduling
    (with Sungjin Im and Ben Moseley).
    WAOA 2009.
  • Online Scheduling to Minimize the Maximum Delay Factor
    (with Ben Moseley).
    SODA 2009. A preliminary ArXiv version here.
  • 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

  • Topology Formation for Wirleless Mesh Network Planning
    Chun-cheng Chen, Chandra Chekuri, Diego Klabjan.
    INFOCOM Mini-Conference, 2009.
  • 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.