18 citations · 45 across the 16 of their papers we have counts for
7 papers · 1 filter
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…