68 citations · 265 across the 47 of their papers we have counts for
56 papers
Approximation Algorithms for Network Design in Non-Uniform Fault Models
Chandra Chekuri, Rhea Jain
The Survivable Network Design problem (SNDP) is a well-studied problem, motivated by the design of networks that are robust to faults under the assumption that any subset of edges…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
Independent Sets in Elimination Graphs with a Submodular Objective
Chandra Chekuri, Kent Quanrud
Maximum weight independent set (MWIS) admits a -approximation in inductively -independent graphs and a -approximation in -perfectly orientable graphs.…
Efficient parallel implementation of the multiplicative weight update method for graph-based linear programs
Caleb Ju, Serif Yesil, Mengyuan Sun +2
Positive linear programs (LPs) model many graph and operations research problems. One can solve for a -approximation for positive LPs, for any selected , in polylogarithm…
On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms
Chandra Chekuri, Manuel R. Torres
Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical problems here are to find a maxcore (subgraph of maxi…
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Q…