CCChandra Chekuri

Chandra Chekuri

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Chandra Chekuri has a total of 65 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Hedgegraph Polymatroids

    by Karthekeyan Chandrasekaran, Chandra Chekuri, Weihang Wang, Weihao Zhu

  • Open Access

    A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection

    by Chandra Chekuri, Rhea Jain

    We consider Buy-at-Bulk Network Design with Protection, which is motivated by fault-tolerance in high speed (optical) networks. Given a graph G=(V,E) and a set of demand pairs (s1,t1), …,(sr,tr), the goal is to route a demand of δ(i) for each pair (si,ti) along two internally vertex-disjoint paths (to protect against a vertex failure) so as to minimize the total cost of routing. The cost of the routing is ∑e fe(xe), where xe is the total flow on edge e and fe: ℝ+ → ℝ+ is a sub-additive cost function that models economies of scale for installing capacity on e. We obtain a polylogarithmic approximation for this problem. The algorithm is based on connections and insights from length-constrained network design. Along the way, we obtain a bicriteria approximation algorithm for a 2-vertex connected length-constrained problem, which is of independent interest.

  • Open Access

    Approximation algorithms for network design in non-uniform fault models

    by Chandra Chekuri, Rhea Jain

    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.


  • Open Access

    Cycle Cancellation for Submodular Fractional Allocations and Applications

    by Chandra Chekuri, Pooja Kulkarni, Ruta Mehta, Jan Vondrak

    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.

  • Open Access

    Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

    by Elfarouk Harb, Yousef Yassin, Chandra Chekuri

    We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic \textsc{SuperGreedy++} act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why \textsc{SuperGreedy++} is effective beyond DSS, including for tasks like submodular minimization and minimum $ s $-$ t $ cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.

  • Polyhedral aspects of feedback vertex set and pseudoforest deletion set

    by Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini, Shubhang Kulkarni, Stefan Weltge


  • Open Access

    On Sparsest Cut and Conductance in Directed Polymatroidal Networks

    by Chandra Chekuri, Anand Louis

    We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flows and cuts in polymatrodial networks \cite{ChekuriKRV15}. We obtain three results. First, we obtain an $O(\sqrt{\log n})$-approximation for sparsest cut and point out how this generalizes the result in \cite{ChenOT23}. Second, we consider the symmetric version of conductance and obtain an $O(\sqrt{OPT \log r})$ approximation where $r$ is the maximum degree and we point out how this generalizes previous work on vertex expansion in graphs. Third, we prove a non-constructive Cheeger like inequality that generalizes previous work on hypergraphs. We provide a unified treatment via line-embeddings which were shown to be effective for submodular cuts in \cite{ChekuriKRV15}.

  • Open Access

    A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs

    by Chandra Chekuri, Rhea Jain

    We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is a directed edge-weighted graph $G = (V, E)$ and a collection of vertex pairs $\{(s_i, t_i)\}_{i \in [k]}$. The goal is to find a minimum cost subgraph $H$ of $G$ such that $H$ contains an $s_i$-$t_i$ path for each $i \in [k]$. DSF is NP-Hard and is known to be hard to approximate to a factor of $Ω(2^{\log^{1 - ε}(n)})$ for any fixed $ε> 0$ [DK'99]. DSF admits approximation ratios of $O(k^{1/2 + ε})$ [CEGS'11] and $O(n^{2/3 + ε})$ [BBMRY'13]. In this work we show that in planar digraphs, an important and useful class of graphs in both theory and practice, DSF is much more tractable. We obtain an $O(\log^6 k)$-approximation algorithm via the junction tree technique. Our main technical contribution is to prove the existence of a low density junction tree in planar digraphs. To find an approximate junction tree we rely on recent results on rooted directed network design problems [FM'23, CJKZZ'24], in particular, on an LP-based algorithm for the Directed Steiner Tree problem [CJKZZ'24]. Our work and several other recent ones on algorithms for planar digraphs [FM'23, KS'21, CJKZZ'24] are built upon structural insights on planar graph reachability and shortest path separators [Thorup'04].

  • Open Access

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

    by Chandra Chekuri, Rhea Jain

    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.

  • Open Access

    1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

    by Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

    We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.