Kent Quanrud

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 59

Top Topics

Approximation Algorithms

Independent Set

Integer Program

Top Venues

Publications

Chandra Chekuri, Aleksander Bjørn Grodt Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, Chris Schwiegelshohn
Adaptive Out-Orientations with Applications. SODA (2024)
Kent Quanrud
Quotient sparsification for submodular functions. SODA (2024)
Kent Quanrud
Faster exact and approximation algorithms for packing and covering matroids via push-relabel. SODA (2024)
Yufan Huang, Peter Jin, Kent Quanrud
Faster single-source shortest paths with negative real weights via proper hop distance. CoRR (2024)
Kent Quanrud
Adaptive Sparsification for Matroid Intersection. ICALP (2024)
Kent Quanrud
Faster exact and approximation algorithms for packing and covering matroids via push-relabel. CoRR (2023)
Chandra Chekuri, Kent Quanrud
Independent Sets in Elimination Graphs with a Submodular Objective. APPROX/RANDOM (2023)
Chandra Chekuri, Kent Quanrud
Independent Sets in Elimination Graphs with a Submodular Objective. CoRR (2023)
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. ESA (2023)
Chandra Chekuri, Aleksander Bjørn Grodt Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, Chris Schwiegelshohn
Adaptive Out-Orientations with Applications. CoRR (2023)
Richard Li, Kent Quanrud
Approximate Fully Dynamic Directed Densest Subgraph. CoRR (2023)
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. CoRR (2023)
Kent Quanrud
Fast and Deterministic Approximations for k-Cut. Theory Comput. 18 (2022)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
Minimum Cuts in Directed Graphs via Partial Sparsification. FOCS (2022)
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Faster and Scalable Algorithms for Densest Subgraph and Decomposition. NeurIPS (2022)
Chandra Chekuri, Tanmay Inamdar, Kent Quanrud, Kasturi R. Varadarajan, Zhao Zhang
Algorithms for covering multiple submodular constraints and applications. J. Comb. Optim. 44 (2) (2022)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. SODA (2022)
Chandra Chekuri, Kent Quanrud
(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time. CoRR (2022)
Kent Quanrud
Fast Approximations for Rooted Connectivity in Weighted Directed Graphs. CoRR (2021)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, Thatchaphol Saranurak
Minimum Cuts in Directed Graphs via Partial Sparsification. CoRR (2021)
Chandra Chekuri, Kent Quanrud
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems. CoRR (2021)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
Minimum Cuts in Directed Graphs via Partial Sparsification. FOCS (2021)
Elena Grigorescu, Young-San Lin, Kent Quanrud
Online Directed Spanners and Steiner Forests. CoRR (2021)
Chandra Chekuri, Kent Quanrud
Faster Algorithms for Rooted Connectivity in Directed Graphs. CoRR (2021)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems. APPROX-RANDOM (2021)
Elena Grigorescu, Young-San Lin, Kent Quanrud
Online Directed Spanners and Steiner Forests. APPROX-RANDOM (2021)
Kent Quanrud
Spectral Sparsification of Metrics and Kernels. SODA (2021)
Chandra Chekuri, Kent Quanrud
Faster Algorithms for Rooted Connectivity in Directed Graphs. ICALP (2021)
Chandra Chekuri, Kent Quanrud
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity. ICALP (2021)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
-Sparsity approximation bounds for packing integer programs. Math. Program. 183 (1) (2020)
Sally Dong, Yin Tat Lee, Kent Quanrud
Computing Circle Packing Representations of Planar Graphs. SODA (2020)
Chandra Chekuri, Kent Quanrud, Chao Xu
LP Relaxation and Tree Packing for Minimum k-Cut. SIAM J. Discret. Math. 34 (2) (2020)
Kent Quanrud
Nearly linear time approximations for mixed packing and covering problems without data structures or randomization. SOSA (2020)
Chandra Chekuri, Sariel Har-Peled, Kent Quanrud
Fast LP-based Approximations for Geometric Packing and Covering Problems. SODA (2020)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems. CoRR (2020)
Chandra Chekuri, Kent Quanrud
Submodular Function Maximization in Parallel via the Multilinear Relaxation. SODA (2019)
Chandra Chekuri, Kent Quanrud, Chao Xu
LP Relaxation and Tree Packing for Minimum k-cuts. SOSA (2019)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
\ell _1 -sparsity Approximation Bounds for Packing Integer Programs. IPCO (2019)
Chandra Chekuri, Kent Quanrud
Parallelizing greedy for submodular set function maximization in matroids and beyond. STOC (2019)
Sally Dong, Yin Tat Lee, Kent Quanrud
Computing Circle Packing Representations of Planar Graphs. CoRR (2019)
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs. CoRR (2019)
Kent Quanrud
Fast and Deterministic Approximations for k-Cut. APPROX-RANDOM (2019)
Chandra Chekuri, Kent Quanrud
On Approximating (Sparse) Covering Integer Programs. SODA (2019)
Chandra Chekuri, Kent Quanrud, Zhao Zhang
On Approximating Partial Set Cover and Generalizations. CoRR (2019)
Kent Quanrud
Approximating Optimal Transport With Linear Programs. SOSA (2019)
Chandra Chekuri, Kent Quanrud
Submodular Function Maximization in Parallel via the Multilinear Relaxation. CoRR (2018)
Chandra Chekuri, Kent Quanrud
Fast Approximations for Metric-TSP via Linear Programming. CoRR (2018)
Chandra Chekuri, Kent Quanrud, Chao Xu
LP Relaxation and Tree Packing for Minimum k-cuts. CoRR (2018)
Kent Quanrud
Fast and Deterministic Approximations for k-Cut. CoRR (2018)
Kent Quanrud
Approximating optimal transport with linear programs. CoRR (2018)
Chandra Chekuri, Kent Quanrud
On Approximating (Sparse) Covering Integer Programs. CoRR (2018)
Chandra Chekuri, Kent Quanrud
Parallelizing greedy for submodular set function maximization in matroids and beyond. CoRR (2018)
Chandra Chekuri, Kent Quanrud
Randomized MWU for Positive LPs. SODA (2018)
Chandra Chekuri, Kent Quanrud
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. FOCS (2017)
Chandra Chekuri, Kent Quanrud
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. CoRR (2017)
Sariel Har-Peled, Kent Quanrud
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs. SIAM J. Comput. 46 (6) (2017)
Chandra Chekuri, Kent Quanrud
Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems. SODA (2017)
Sariel Har-Peled, Kent Quanrud
Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs. CoRR (2016)
Chandra Chekuri, Kent Quanrud
A Fast Approximation for Maximum Weight Matroid Intersection. SODA (2016)
Sariel Har-Peled, Kent Quanrud
Approximation Algorithms for Low-Density Graphs. CoRR (2015)
Kent Quanrud, Daniel Khashabi
Online Learning with Adversarial Delays. NIPS (2015)
Chandra Chekuri, Shalmoli Gupta, Kent Quanrud
Streaming Algorithms for Submodular Function Maximization. ICALP (1) (2015)
Sariel Har-Peled, Kent Quanrud
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs. ESA (2015)
Chandra Chekuri, Shalmoli Gupta, Kent Quanrud
Streaming Algorithms for Submodular Function Maximization. CoRR (2015)