18 citations · 45 across the 16 of their papers we have counts for
26 papers
Approximating Directed Connectivity in Almost-Linear Time
Kent Quanrud
We present randomized algorithms that compute -approximate minimum global edge and vertex cuts in weighted directed graphs in and single-…
Approximate Fully Dynamic Directed Densest Subgraph
Richard Li, Kent Quanrud
We give a fully dynamic algorithm maintaining a -approximate directed densest subgraph in amortized time or $\tilde{O}(\log^4(…
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.…
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…
Faster exact and approximation algorithms for packing and covering matroids via push-relabel
Kent Quanrud
Matroids are a fundamental object of study in combinatorial optimization. Three closely related and important problems involving matroids are maximizing the size of the union of $k…
-approximate fully dynamic densest subgraph: linear space and faster update time
Chandra Chekuri, Kent Quanrud
We consider the problem of maintaining a -approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dy…
Minimum Cuts in Directed Graphs via Partial Sparsification
Ruoxu Cen, Jason Li, Danupon Nanongkai +3
We give an algorithm to find a minimum cut in an edge-weighted directed graph with vertices and edges in time. This improves on the 30 y…
Faster Algorithms for Rooted Connectivity in Directed Graphs
Chandra Chekuri, Kent Quanrud
We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and…
Fast Approximations for Rooted Connectivity in Weighted Directed Graphs
Kent Quanrud
We consider approximations for computing minimum weighted cuts in directed graphs. We consider both rooted and global minimum cuts, and both edge-cuts and vertex-cuts. For these pr…
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems
Chandra Chekuri, Kent Quanrud
Li and Panigrahi, in recent work, obtained the first deterministic algorithm for the global minimum cut of a weighted undirected graph that runs in time . They introduced an…
Online Directed Spanners and Steiner Forests
Elena Grigorescu, Young-San Lin, Kent Quanrud
We present online algorithms for directed spanners and Steiner forests. These problems fall under the unifying framework of online covering linear programming formulations, develop…
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing…
Computing Circle Packing Representations of Planar Graphs
Sally Dong, Yin Tat Lee, Kent Quanrud
The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Pr…
On Approximating Partial Set Cover and Generalizations
Chandra Chekuri, Kent Quanrud, Zhao Zhang
Partial Set Cover (PSC) is a generalization of the well-studied Set Cover problem (SC). In PSC the input consists of an integer and a set system where is a finite s…
Parallelizing greedy for submodular set function maximization in matroids and beyond
Chandra Chekuri, Kent Quanrud
We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to se…
Approximating optimal transport with linear programs
Kent Quanrud
In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear…
LP Relaxation and Tree Packing for Minimum -cuts
Chandra Chekuri, Kent Quanrud, Chao Xu
Karger used spanning tree packings to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts…
On Approximating (Sparse) Covering Integer Programs
Chandra Chekuri, Kent Quanrud
We consider approximation algorithms for covering integer programs of the form min over subject to and ; where…
Submodular Function Maximization in Parallel via the Multilinear Relaxation
Chandra Chekuri, Kent Quanrud
Balkanski and Singer [5] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality cons…
Fast and Deterministic Approximations for -Cut
Kent Quanrud
In an undirected graph, a -cut is a set of edges whose removal breaks the graph into at least connected components. The minimum weight -cut can be computed in $O(n^{O(k)}…
Fast Approximations for Metric-TSP via Linear Programming
Chandra Chekuri, Kent Quanrud
We develop faster approximation algorithms for Metric-TSP building on recent, nearly linear time approximation schemes for the LP relaxation [Chekuri and Quanrud, 2017]. We show th…
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time
Chandra Chekuri, Kent Quanrud
We give a nearly linear time randomized approximation scheme for the Held-Karp bound [Held and Karp, 1970] for metric TSP. Formally, given an undirected edge-weighted graph on…
Adversarial Delays in Online Strongly-Convex Optimization
Daniel Khashabi, Kent Quanrud, Amirhossein Taghvaei
We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbi…
Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
Sariel Har-Peled, Kent Quanrud
This write-up contains some minor results and notes related to our work [HQ15] (some of them already known in the literature). In particular, it shows the following: - We show that…