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

  • Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
    (with Rhea Jain).
    Manuscript, April 2024.

  • Approximation Algorithms for Network Design in Non-Uniform Fault Models
    (with Rhea Jain).
    Paper has improvements and some extensions over an ICALP 2023 paper which itself combined and extended results from two earlier manuscripts.

  • 1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations
    (with Pooja Kulkarni, Rucha Kulkarni and Ruta Mehta).
    AAAI, 2024.

  • Contention Resolution for the l-fold union of a matroid via the correlation gap
    (with Junkai Song and Weizhong Zhang).
    SOSA, 2024.

  • Adaptive Out-Orientations with Applications
    (with Aleksander Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, Chris Schwiegelshohn).
    SODA, 2024.

  • Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs
    (with Caleb Ju, Serif Yesil, Mengyuan Sun, and Edgar Solomonik).
    Manuscript, July 2023.

  • Improved Throughput for All-or-Nothing Multicommodity Flows with Arbitrary Demands
    (with Anya Chaturvedi, Andr\'ea W. Richa, Mattias Rost, Stefan Schmid, Jamison Weber).
    IEEE Transactions on Networking, 2023. Preliminary version appeared as a short paper in Performance 2021.

  • On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms
    (with Manuel Torres).
    Manuscript, February 2023.

  • Independent Sets in Elimination Graphs with a Submodular Objective
    (with Kent Quanrud).
    APPROX 2023.

  • Bicriteria Approximation Algorithms for Priority Matroid Median
    (with Tanvi Bajpai).
    APPROX 2023.

  • Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
    (with ElFarouk Harb and Kent Quanrud).
    ESA Track S, 2023.

  • Minmax Partitioning of Hypergraphs and Symmetric Submodular Functions
    (with Karthik Chandrasekaran).
    Combinatorica, April 2023. Preliminary version in ACM-SIAM SODA 2021.

  • Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
    (with Karthik Chandrasekaran, Sam Fiorini, Shubhang Kulkarni, and Stefan Weltge).
    Manuscript, Mar 2023.

  • Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
    (with Calvin Beideman, Karthik Chandrasekaran and Chao Xu).
    FSTTCS 2022.

  • Faster and Scalable Algorithms for Densest Subgraph and Decomposition
    (with ElFarouk Harb and Kent Quanrud).
    NeuRIPS 2022.

  • Algorithms for Intersection Graphs of t-Intervals and t-Pseudodisks
    (with Tanmay Inamdar).
    Short communication in Theory of Computing, 2022. ArXiv version, 2019.

  • Algorithms for Covering Multiple Submodular Constraints and Applications
    (with Tanmay Inamdar, Kent Quanrud, Kasturi Varadarajan and Zhao Zhang).
    Journal of Combinatorial Optimization, June 2022. Manuscript, 2020.

  • Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
    (with Kent Quanrud and Manuel Torres).
    SODA 2022.

  • On Submodular Prophet Inequalities and Correlation Gap
    (with Vasilis Livanos).
    SAGT 2021.

  • Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
    (with Kent Quanrud and Manuel Torres).
    Manuscript, July 2020. APPROX 2021.

  • Faster Algorithms for Rooted Connectivity in Directed Graphs
    (with Kent Quanrud).
    Manuscript, November 2020, updated April 2021. ICALP 2021.

  • Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems
    (with Kent Quanrud).
    Manuscript, November 2020. ICALP 2021.

  • Revisiting Priority k-Center: Fairness and Outliers
    (with Tanvi Bajpai, Deeparnab Chakrabarty and Maryam Negahbani)
    Manuscript, November 2021. ICALP 2021.

  • Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    (with Alina Ene and Ali Vakilian).
    ACM Transactions on Algorithms, 17(2), June 2021. Manuscript, October 2019.
    Note: This is an update/extension to an ICALP 2012 paper with the same title. The ICALP paper was on EC-SNDP and this one handles Element SNDP and indirectly VC-SNDP.

  • On the hardness of the k-way Hypergraph Cut problem
    (with Shi Li)
    Short note in Theory of Computing, 16:1-8, Dec 2020.
    Manuscript, November 2015    .

  • Hypergraph k-cut for fixed k in deterministic polynomial time
    (with Karthik Chandrasekaran).
    Math of OR, 2022. Preliminary version in FOCS 2020. ArXiv version.

  • LP Relaxation and Tree Packings for Minimum k-Cut
    (with Kent Quanrud and Chao Xu).
    SIAM J. on Discrete Math, 2020.
    Preliminary version in SOSA 2019.
    Note: The paper incorrectly credits the Gomory-Hu tree based approximation algorithm for k-cut to Saran-Vazirani. It appears that the algorithm should be credited to the independent work Sanjiv Kapoor (see his IPCO'96 paper) and R. Ravi (see Vazirani's approx algorithms book).

  • ℓ1-sparsity Approximation bounds for Packing Integer Programs
    (with Kent Quanrud and Manuel Torres).
    Mathematical Programming Ser B, published online Feb 2020. Special issue for papers from IPCO 2019.

  • Fast LP-based Approximations for Geometric Packing and Covering Problems
    (with Sariel Har-Peled and Kent Quanrud).
    SODA 2020.

  • Parallelizing greedy for submodular set function maximization in matroids and beyond
    (with Kent Quanrud).
    STOC 2019.

  • Submodular Function Maximization in Parallel via the Multilinear Relaxation
    (with Kent Quanrud).
    SODA 2019.

  • On Approximating (Sparse) Covering Integer Programs
    (with Kent Quanrud).
    SODA 2019.

  • Minimum cuts and sparsification in hypergraphs
    (with Chao Xu).
    SIAM Journal on Computing, 47(6): 2118-2156, 2018.
    Combines results from a SODA 2017 paper and an unpublished manuscript that you can find below.

  • Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations
    (with Shalmoli Gupta).
    APPROX, 2018.

  • Fast Approximations for Metric-TSP via Linear Programming
    (with Kent Quanrud).
    Manuscript, 2018.

  • Congestion minimization for multipath routing via multiroute flows
    (with Mark Idleman).
    SOSA 2018.

  • A note on the Survivable Network Design Problem
    (with Thapanapong Rukkanchanunt).
    Manuscript, August 2016. SOSA 2018.

  • Randomized MWU for Positive LPs
    (with Kent Quanrud).
    SODA 2018.

  • Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
    (with Alina Ene and Marcin Pilipczuk)
    SIAM Journal on Discrete Mathematics, 32(3): 2134-2160, 2018. Preliminary version in ICALP 2016.

  • A note on approximate strengths of edges in a hypergraph
    (with Chao Xu).
    Manuscript, March 2017.

  • Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time
    (with Kent Quanrud).
    FOCS 2017.

  • Polynomial Bounds for the Grid-Minor Theorem
    (with Julia Chuzhoy).
    Journal of the ACM, Dec 2016. Extended abstract in STOC 2014.
    ArXiv version.

  • Computing minimum cuts in hypergraphs
    (with Chao Xu).
    SODA 2017.
    Note: The SODA camera ready version has a bug in the sparsification section that is fixed in the ArXiv update.

  • Approximating Multicut and the Demand Graph
    (with Vivek Madan).
    SODA 2017.

  • Near-linear-time approximation schemes for some implicit fractional packing problems
    (with Kent Quanrud).
    SODA 2017.

  • Some Open Problems in Element Connectivity
    Manuscript, September 2015.

  • Constant Factor Approximation for Subset Feedback Problems via a new LP relaxation
    (with Vivek Madan).
    SODA 2016.

  • A Fast Approximation for Maximum Weight Matroid Intersection
    (with Kent Quanrud).
    SODA 2016.

  • Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
    (with Vivek Madan).
    SODA 2016.

  • Multicommodity Flows and Cuts in Polymatroidal Networks
    (with Sreeram Kannan, Adnan Raja and Pramod Viswanath).
    SIAM J. on Computing 44(4): 912 - 943, 2015.
    Combines a preliminary version that appeared in Proceedings of ITCS 2012 and subsequent work on minor-free graphs.

  • On Element-Connectivity Preserving Graph Simplification
    (with Thapanapong Rukkanchanunt and Chao Xu).
    ESA 2015.

  • Streaming Algorithms for Submodular Function Maximization
    (with Shalmoli Gupta and Kent Quanrud).
    Extended abstract in ICALP 2015.
    Note: The algorithm in Sec 4.7 that claims an improved approximation for the cardinality constraint is incorrect. See paper of Alaluf and Feldman.

  • Delay-constrained Unicast and the Triangle-cast Problem
    (with Sudeep Kamath, Sreeram Kannan and Pramod Viswanath).
    ISIT 2015.

  • On Multiplicative Weight Updates for Concave and Submodular Function Maximization
    (with Jayram Thathachar and Jan Vondrak).
    Extended abstract in ITCS 2015.

  • Degree-3 Treewidth Sparsifiers
    (with Julia Chuzhoy).
    Extended abstract in SODA 2015.

  • Centrality of Trees for Capacitated k-Center
    (with Hyung-Chan An, Aditya Bhaskara, Shalmoli Gupta, Vivek Madan and Ola Svensson).
    Mathematical Programming Ser B. 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.

  • The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    (with Alina Ene).
    Mathematical Programming Ser B, December, 2014. 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.

    • Approximation Algorithms and Combinatorial Optimization

  • Computing minimum cuts in hypergraphs
    (with Chao Xu).
    SODA 2017.
    Note: The SODA camera ready version has a bug in the sparsification section that is fixed in the ArXiv update.

  • Approximating Multicut and the Demand Graph
    (with Vivek Madan).
    SODA 2017.

  • Near-linear-time approximation schemes for some implicit fractional packing problems
    (with Kent Quanrud).
    SODA 2017.

  • Polynomial Bounds for the Grid-Minor Theorem
    (with Julia Chuzhoy).
    Journal of the ACM, Dec 2016. Extended abstract in STOC 2014.
    ArXiv version.

  • A note on the Survivable Network Design Problem
    (with Thapanapong Rukkanchanunt).
    Manuscript, August 2016.

  • Some Open Problems in Element Connectivity
    Manuscript, September 2015.

  • Constant Factor Approximation for Subset Feedback Problems via a new LP relaxation
    (with Vivek Madan).
    SODA 2016.

  • A Fast Approximation for Maximum Weight Matroid Intersection
    (with Kent Quanrud).
    SODA 2016.

  • Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
    (with Vivek Madan).
    SODA 2016.

  • Multicommodity Flows and Cuts in Polymatroidal Networks
    (with Sreeram Kannan, Adnan Raja and Pramod Viswanath).
    SIAM J. on Computing 44(4): 912 - 943, 2015.
    Combines a preliminary version that appeared in Proceedings of ITCS 2012 and subsequent work on minor-free graphs.

  • On Multiplicative Weight Updates for Concave and Submodular Function Maximization
    (with Jayram Thathachar and Jan Vondrak).
    Extended abstract in ITCS 2015.

  • Degree-3 Treewidth Sparsifiers
    (with Julia Chuzhoy).
    Extended abstract in SODA 2015.

  • Centrality of Trees for Capacitated k-Center
    (with Hyung-Chan An, Aditya Bhaskara, Shalmoli Gupta, Vivek Madan and Ola Svensson).
    Mathematical Programming Ser B. 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.

  • The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs
    (with Alina Ene).
    Mathematical Programming Ser B, December, 2014. 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.

  • Node-weighted Network Design in Planar and Minor-closed Families of Graphs
    (with Alina Ene and Ali Vakilian).
    ICALP 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).
    SICOMP 43(6): 1831–1879, 2014.
    Shorter version in STOC 2011.

  • Approximability of Capacitated Network Design
    (with Deeparnab Chakrabarty, Sanjeev Khanna and Nitish Korula).
    Algorithmica, 72(2): 493–514, 2015. Preliminary version in 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.
    A journal version with one application removed appeared in SIAM J. on Discrete Math, 2014. The other application is describe in detail in Nitish Korula's PhD thesis.

  • 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. Nitish's thesis has the proofs.

  • Pruning 2-Connected Graphs
    (with Nitish Korula).
    Algorithmica, published online November 2010. Short version in FSTTCS, December 2008.
    Preliminary version on ArXiv with a different title.

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

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

  • 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 in 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.
    ICDT 2016 Test of Time Award

    • Miscellaneous

  • Delay-constrained Unicast and the Triangle-cast Problem
    (with Sudeep Kamath, Sreeram Kannan and Pramod Viswanath).
    ISIT 2015.

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