Kent Quanrud

Assistant Professor, Theory Group
Dept. of Computer Science, Purdue University


Lawson 1211

My research is about the design and analysis of algorithms in theoretical computer science. I have worked on approximation algorithms, randomized algorithms, combinatorial optimization, continuous optimization, online learning, and discrete geometry. I am particularly interested in highly scalable algorithms for fundamental problems in optimization.

Teaching

Course materials available at the links above.

Research

My research is supported in part by NSF. See DBLP for a more up-to-date list.

whatwherewith whoslides & more
Quotient sparsification for submodular functionsManuscript, Nov. 2022Dagstuhl, Simons
Faster exact and approximation algorithms for packing and covering matroids via push-relabelManuscript, July 2022 
(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update timeManuscript, July 2022Chandra Chekuri 
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree PackingESA (Track S) 2023Chandra Chekuri and Elfarouk Harb 
Independent Sets in Elimination Graphs with a Submodular ObjectiveAPPROX 2023Chandra Chekuri 
Faster and Scalable Algorithms for Densest Subgraph and DecompositionNeuRIPS 2022Chandra Chekuri and Elfarouk Harb 
Densest Subgraph: Supermodularity, Iterative Peeling, and FlowSODA 2022Chandra Chekuri and Manuel Torres 
Algorithms for covering multiple submodular constraints and applicationsJournal of Combinatorial Optimization, 2022Chandra Chekuri, Tanmay Inamdar, Kasturi Varadarajan, and Zhao Zhang 
Minimum Cuts in Directed Graphs via Partial SparsificationFOCS 2021Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak 
Faster Algorithms for Rooted Connectivity in Directed GraphsICALP 2021Chandra Chekuri 
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity ProblemsICALP 2021Chandra Chekuri 
Spectral Sparsification for Metrics and KernelsSODA 2021SODA
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree ProblemsAPPROX 2021Chandra Chekuri and Manuel Torres 
Online Directed Spanners and Steiner ForestsAPPROX 2021Elena Grigorescu and Young-San Lin 
Circle Packing of Planar Graphs in Nearly Linear TimeSODA 2020Sally Dong and Yin Tat Lee 
Fast LP-based Approximations for Geometric Packing and Covering ProblemsSODA 2020Chandra Chekuri and Sariel Har-Peled 
Nearly linear time approximations for mixed packing and covering problems without data structures or randomizationSOSA@SODA 2020SOSA
1‑Sparsity Approximation Bounds for Packing Integer Programs.Math Program. 2020, IPCO 2019Chandra Chekuri and Manuel R. Torres 
Fast and Deterministic Approximations for k‑cutAPPROX 2019APPROX
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and BeyondSTOC 2019Chandra ChekuriBellairs, MSR, Purdue, NWU
Approximating Optimal Transport with Linear ProgramsSOSA 2019SOSA
LP Relaxation and Tree Packings for Minimum k‑cutSOSA 2019Chandra Chekuri and Chao Xu 
On Approximating (Sparse) Covering Integer ProgramsSODA 2019Chandra ChekuriSODA
Submodular Function Maximization in Parallel via the Multilinear RelaxationSODA 2019Chandra ChekuriBellairs, MSR, Purdue, NWU, SODA, Allerton
Fast Approximations for Metric‑TSP via Linear ProgrammingarXiv 2018Chandra ChekuriBIRS (video, slides), ISMP, UIUC
Randomized MWU for Positive LPsSODA 2018Chandra ChekuriSODA
Approximation Algorithms for Polynomial Expansion and Low‑Density GraphsSIAM J. Comput. (SICOMP) 2017
ESA 2015
Sariel Har-PeledUIUC, add'l notes
Approximating the Held‑Karp Bound for Metric TSP in Nearly Linear TimeFOCS 2017
Invited to HALG 2018
Chandra ChekuriBIRS (video, slides), ISMP, FOCS (videoslides)
Near‑Linear‑Time Approximation Schemes for some Implicit Fractional Packing ProblemsSODA 2017Chandra ChekuriSODA, Bellairs
A Fast Approximation for Maximum Weight Matroid IntersectionSODA 2016Chandra ChekuriSODA, UIUC
Streaming Algorithms for Submodular Function MaximizationICALP 2015Chandra Chekuri and Shalmoli GuptaBonn (video, slides)
Online Learning with Adversarial DelaysNIPS 2015Daniel KhashabiNIPS

Quotient sparsification for submodular functions

Manuscript, Nov. 2022

slides: Dagstuhl, Simons

Faster exact and approximation algorithms for packing and covering matroids via push-relabel

Manuscript, July 2022

(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time

Manuscript, July 2022

with Chandra Chekuri

Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing

ESA (Track S) 2023

with Chandra Chekuri and Elfarouk Harb

Independent Sets in Elimination Graphs with a Submodular Objective

APPROX 2023

with Chandra Chekuri

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

NeuRIPS 2022

with Chandra Chekuri and Elfarouk Harb

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

SODA 2022

with Chandra Chekuri and Manuel Torres

Algorithms for covering multiple submodular constraints and applications

Journal of Combinatorial Optimization, 2022

with Chandra Chekuri, Tanmay Inamdar, Kasturi Varadarajan, and Zhao Zhang

Minimum Cuts in Directed Graphs via Partial Sparsification

FOCS 2021

with Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak

Faster Algorithms for Rooted Connectivity in Directed Graphs

ICALP 2021

with Chandra Chekuri

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems

ICALP 2021

with Chandra Chekuri

Spectral Sparsification for Metrics and Kernels

SODA 2021

slides: SODA

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems

APPROX 2021

with Chandra Chekuri and Manuel Torres

Online Directed Spanners and Steiner Forests

APPROX 2021

with Elena Grigorescu and Young-San Lin

Circle Packing of Planar Graphs in Nearly Linear Time

SODA 2020

with Sally Dong and Yin Tat Lee

Fast LP-based Approximations for Geometric Packing and Covering Problems

SODA 2020

with Chandra Chekuri and Sariel Har-Peled

Nearly linear time approximations for mixed packing and covering problems without data structures or randomization

SOSA@SODA 2020

slides: SOSA

1‑Sparsity Approximation Bounds for Packing Integer Programs.

Math Program. 2020, IPCO 2019

with Chandra Chekuri and Manuel R. Torres

Fast and Deterministic Approximations for k‑cut

APPROX 2019

slides: APPROX

Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond

STOC 2019

with Chandra Chekuri

slides: Bellairs, MSR, Purdue, NWU

Approximating Optimal Transport with Linear Programs

SOSA 2019

slides: SOSA

LP Relaxation and Tree Packings for Minimum k‑cut

SOSA 2019

with Chandra Chekuri and Chao Xu

On Approximating (Sparse) Covering Integer Programs

SODA 2019

with Chandra Chekuri

slides: SODA

Submodular Function Maximization in Parallel via the Multilinear Relaxation

SODA 2019

with Chandra Chekuri

slides: Bellairs, MSR, Purdue, NWU, SODA, Allerton

Fast Approximations for Metric‑TSP via Linear Programming

arXiv 2018

with Chandra Chekuri

slides: BIRS (video, slides), ISMP, UIUC

Randomized MWU for Positive LPs

SODA 2018

with Chandra Chekuri

slides: SODA

Approximation Algorithms for Polynomial Expansion and Low‑Density Graphs

SIAM J. Comput. (SICOMP) 2017
ESA 2015

with Sariel Har-Peled

slides: UIUC, add'l notes

Approximating the Held‑Karp Bound for Metric TSP in Nearly Linear Time

FOCS 2017
Invited to HALG 2018

with Chandra Chekuri

slides: BIRS (video, slides), ISMP, FOCS (videoslides)

Near‑Linear‑Time Approximation Schemes for some Implicit Fractional Packing Problems

SODA 2017

with Chandra Chekuri

slides: SODA, Bellairs

A Fast Approximation for Maximum Weight Matroid Intersection

SODA 2016

with Chandra Chekuri

slides: SODA, UIUC

Streaming Algorithms for Submodular Function Maximization

ICALP 2015

with Chandra Chekuri and Shalmoli Gupta

slides: Bonn (video, slides)

Online Learning with Adversarial Delays

NIPS 2015

with Daniel Khashabi

slides: NIPS