About

Chandra Chekuri is the Paul and Cynthia Saylor Professor at the Siebel School of Computing and Data Science at the University of Illinois Urbana-Champaign. He holds a Ph.D. in Computer Science from Stanford University and a B.Tech in Computer Science from the Indian Institute of Technology, Madras. His research areas include Theory and Algorithms, with a focus on topics such as combinatorial optimization, graph algorithms, submodular function maximization, and approximation algorithms. Chekuri has made significant contributions to the understanding of minimum cuts, sparsification in hypergraphs, grid-minor theorems, multicommodity flows, and cuts in polymatroidal networks, among other areas. He has served as editor-in-chief of the SIAM Journal on Computing and has been recognized as an ACM Fellow in 2024. Chekuri is known for his leadership in the field, organizing major conferences and contributing to the academic community through editorial roles and research.

Research topics

• Discrete mathematics
• Combinatorics
• Mathematics
• Algorithm
• Computer Science
• Mathematical optimization

Selected publications

• Uncrossed Multiflows and Applications to Disjoint Paths

  ArXiv.org · 2025-10-31

  preprintOpen access1st authorCorresponding

  A multiflow in a planar graph is uncrossed if its support paths do not cross. Recently such flows played a role in approximation algorithms for maximum disjoint paths in "fully-planar" instances, where the combined supply-demand graph is planar, as well as low-congestion unsplittable flows for fully-planar and single-source instances. We expand on the theory of uncrossed flows to investigate their utility more generally. We ask three key questions. First, are there other interesting planar multiflow instances that admit uncrossed flows? We answer affirmatively, demonstrating a new family of "pairwise-planar" instances whose flows can be uncrossed. This family subsumes fully-planar but includes substantially more, such as fully-compliant series-parallel instances, and has instances with clique demand graphs. Second, given a fractional uncrossed flow, can we always round it to a "good" integral flow? We again answer positively. For maximization problems (where we maximize the total amount of flow), we obtain integral flows with a constant fraction of the original value. For congestion problems (where we fully route specific given demands), we obtain integral flows with edge congestion 2, or unsplittable flows with an additional additive error. As a consequence we obtain approximation algorithms for maximum disjoint paths and minimum congestion integer multiflow for pairwise-planar instances. Finally, given a planar multiflow instance, can we determine if there exists a congestion 1 uncrossed fractional flow (congestion) or find the highest value uncrossed fractional flow (maximization)? For the congestion model, we show this is NP-hard, but finding uncrossed edge-disjoint paths is polytime solvable if the demands span a bounded number of faces. For the maximization model, we present a strong inapproximability result.

  PublisherOA PDFDOI

• Online Disjoint Spanning Trees and Polymatroid Bases

  ArXiv.org · 2025-01-01

  preprintOpen access

  Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms [Schrijver, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation [Feige et al., 2002; Cheriyan and Salavatipour, 2007]. Călinescu, Chekuri, and Vondrák [G. Călinescu et al., 2009] viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model [Pananjady et al., 2015; Emek et al., 2019; Bienkowski et al., 2025]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations, we formulate an online model for packing bases of a polymatroid, and describe a randomized algorithm with a polylogarithmic competitive ratio. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [Quanrud, 2024]. We generalize the previously known result for the online disjoint set cover problem [Emek et al., 2019] and also address several other packing problems in a unified fashion. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same poly-logarithmic competitive ratio.

  PublisherOA PDFDOI

• On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions

  ArXiv.org · 2025-01-01

  articleOpen access

  We consider deletion problems in graphs and supermodular functions where the goal is to reduce density. In Graph Density Deletion (GraphDD), we are given a graph $G=(V,E)$ with non-negative vertex costs and a non-negative parameter $ρ\ge 0$ and the goal is to remove a minimum cost subset $S$ of vertices such that the densest subgraph in $G-S$ has density at most $ρ$. This problem has an underlying matroidal structure and generalizes several classical problems such as vertex cover, feedback vertex set, and pseudoforest deletion set for appropriately chosen $ρ\le 1$ and all of these classical problems admit a $2$-approximation. In sharp contrast, we prove that for every fixed integer $ρ> 1$, GraphDD is hard to approximate to within a logarithmic factor via a reduction from Set Cover, thus showing a phase transition phenomenon. Next, we investigate a generalization of GraphDD to monotone supermodular functions, termed Supermodular Density Deletion (SupmodDD). In SupmodDD, we are given a monotone supermodular function $f:2^V \rightarrow \mathbb{Z}_{\ge 0}$ via an evaluation oracle with element costs and a non-negative integer $ρ\ge 0$ and the goal is remove a minimum cost subset $S \subseteq V$ such that the densest subset according to $f$ in $V-S$ has density at most $ρ$. We show that SupmodDD is approximation equivalent to the well-known Submodular Cover problem; this implies a tight logarithmic approximation and hardness for SupmodDD; it also implies a logarithmic approximation for GraphDD, thus matching our inapproximability bound. Motivated by these hardness results, we design bicriteria approximation algorithms for both GraphDD and SupmodDD.

  PublisherOA PDFDOI

• Covering a Few Submodular Constraints and Applications

  ArXiv.org · 2025-01-01

  articleOpen access

  We consider the problem of covering multiple submodular constraints. Given a finite ground set $N$, a cost function $c: N \rightarrow \mathbb{R}_+$, $r$ monotone submodular functions $f_1,f_2,\ldots,f_r$ over $N$ and requirements $b_1,b_2,\ldots,b_r$ the goal is to find a minimum cost subset $S \subseteq N$ such that $f_i(S) \ge b_i$ for $1 \le i \le r$. When $r=1$ this is the well-known Submodular Set Cover problem. Previous work \cite{chekuri2022covering} considered the setting when $r$ is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each $f_i$ is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least $Ω(\log r)$ which is unavoidable when $r$ is part of the input. In this paper, motivated by some recent applications, we consider the problem when $r$ is a \emph{fixed constant} and obtain two main results. For covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer $α\ge 1$ outputs a set $S$ such that $f_i(S) \ge$ $(1-1/e^α-ε)b_i$ for each $i \in [r]$ and $\mathbb{E}[c(S)] \le (1+ε)α\cdot \sf{OPT}$. Second, when the $f_i$ are weighted coverage functions from a deletion-closed set system we obtain a $(1+ε)$ $(\frac{e}{e-1})$ $(1+β)$-approximation where $β$ is the approximation ratio for the underlying set cover instances via the natural LP. These results show that one can obtain nearly as good an approximation for any fixed $r$ as what one would achieve for $r=1$. We mention some applications that follow easily from these general results and anticipate more in the future.

  PublisherOA PDFDOI

• Polyhedral aspects of feedback vertex set and pseudoforest deletion set

  Mathematical Programming · 2025-01-04 · 1 citations

  article
  PublisherDOI

• Approximation algorithms for network design in non-uniform fault models

  Mathematical Programming · 2025-12-01

  articleOpen access1st authorCorresponding

  Abstract The Survivable Network Design problem (SNDP) is a well-studied problem, (partly) motivated by the design of networks that are robust to faults under the assumption that any subset of edges up to a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. We consider three models: the flexible graph connectivity model (Adjiashvili, D.: Fault-tolerant shortest paths - beyond the uniform failure model (unpublished).) (Adjiashvili, D. et al. in Math. Program. 192 (1–2), 409–441 (2022)) (Boyd, S. et al. in Math. Program. pp. 1–24 (2023)) which was our initial motivation, the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61–77. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015)) (Adjiashvili, D. et al,: in Math. Program. 149 (1–2), 361–390 (2015)) and the relative survivable network design model (Dinitz, M. et al.: in Algorithms and Techniques (APPROX/RANDOM 2022), Leibniz International Proceedings in Informatics (LIPIcs), 245 , pp. 41:1–41:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022)) (Dinitz, M. et al.: in Algorithms, pp. 190–204. Springer Nature Switzerland, Cham (2023)). While SNDP admits a 2-approximation (Jain, K.: in Combinatorica 21 (1), 39–60 (2001)), the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when the robustness parameters are fixed constants, we consider two important special cases, namely the single pair case and the global connectivity case. For both these, we obtain constant factor approximations in several parameter ranges of interest. These are based on an augmentation framework and via decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second set of results are poly-logarithmic approximations for the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61–77. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015)) when the “width” of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. The results are obtained via two algorithmic approaches and they have different tradeoffs in terms of the approximation ratio and generality.

  PublisherOA PDFDOI

• A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01 · 1 citations

  book-chapter1st authorCorresponding

  We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is adirected edge-weighted graph G = (V,E ) and a collection of vertex pairs {(si,ti )}i∈[k]. The goal is to find a minimum cost subgraph H of G such that H contains an si -ti path for each i ∈ [k]. DSF is NP-Hard and is known to be hard to approximate to a factor of Ω(2log1-∈ (n )) for any fixed ∈ > 0 [17]. DSF admits approximation ratios of O (K1/2+∈) [10] and O (n2/3+∈) [4].

  PublisherDOI

• Cycle Cancellation for Submodular Fractional Allocations and Applications

  ArXiv.org · 2025-11-26

  preprintOpen access1st authorCorresponding

  We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms. In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease. We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model.

  PublisherOA PDFDOI

• Streaming Algorithms for Network Design

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r(uv) for each u, v ∈ V. The objective is to find a minimum-weight subgraph H ⊆ G such that, for every pair of vertices u, v ∈ V, u and v are r(uv)-edge/vertex-connected. Recent work by [Ce Jin et al., 2024] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). In this work we consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. - We provide a general framework for solving connectivity problems including SNDP and others in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP we provide an O(tk)-approximation in Õ(k^{1-1/t}n^{1 + 1/t}) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(β t)-approximation where β is the integrality gap of the natural cut-based LP relaxation. These are the first approximation algorithms in the streaming model for VC-SNDP. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^{1/2-1/(2t)}n^{1 + 1/t} + kn) space, improving the O(t log k)-approximation of [Ce Jin et al., 2024] using Õ(kn^{1+1/t}) space; this also extends to element-connectivity SNDP. - We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected spanning subgraph G, and additional weighted links L arrive in the stream; the goal is to store the min-weight set of links such that G ∪ L is (k+1)-vertex-connected. We obtain constant-factor approximations in near-linear space for k = 1, 2. Our result for k = 2 is based on using the SPQR tree, a novel application for this well-known representation of 2-connected graphs.

  PublisherOA PDFDOI

• Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

  arXiv (Cornell University) · 2024-01-01

  preprintOpen access1st authorCorresponding

  We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [CHKS09,KN11]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [CHKS09]. The rounding is based on recent results in hop-constrained oblivious routing [GHZ21], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [GL17,GML18,AJL20] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.

  PublisherOA PDFDOI

Recent grants

• AF: Small: Faster and Better Algorithms for, and via, Mathematical Programming Relaxations

  NSF · $300k · 2019–2024

• AF: Small: Approximation Algorithms for Graph and Combinatorial Optimization Problems

  NSF · $487k · 2010–2014

• Approximation Algorithms for Routing and Network Design

  NSF · $292k · 2007–2011

• AF: Small: Optimizing with Submodular Set Functions: Algorithms, Integrality Gaps and Structural Results

  NSF · $450k · 2015–2020

• AF: Small: Flows, Cuts, Treewidth and Algorithms for Routing, Network Design and Related Problems

  NSF · $495k · 2013–2018

Frequent coauthors

• Kent Quanrud

  45 shared

• Sanjeev Khanna

  32 shared

• F. Bruce Shepherd

  University of British Columbia

  24 shared

• Alina Ene

  22 shared

• Nitish Korula

  Google (United States)

  19 shared

• Julia Chuzhoy

  13 shared

• Benjamin Moseley

  Robert Bosch (United States)

  12 shared

• Joseph Naor

  10 shared

Labs

• Siebel School of Computing and Data SciencePI

Education

• Ph.D., Computer Science

  University of California, Berkeley

  2000

• M.S., Computer Science

  University of California, Berkeley

  1996

• B.S., Computer Science

  University of California, Berkeley

  1994

Awards & honors

• ACM Fellow (2024)
• Editor-in-Chief, SIAM Journal on Computing, May 2025 - prese…