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 extremely scalable algorithms for fundamental problems in optimization.

This semester I am co-teaching randomized algorithms (CS590-RA) with Petros Drineas.


whatwherewho elseslides & more
Circle Packing of Planar Graphs in Nearly Linear TimeSODA 2020Sally Dong
Yin Tat Lee
 
Fast LP-based Approximations for Geometric Packing and Covering ProblemsSODA 2020Chandra Chekuri
Sariel Har-Peled
 
Fast and Deterministic Approximations for k‑cutAPPROX 2019 APPROX
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and BeyondSTOC 2019Chandra ChekuriBellairs, MSR, Purdue, NWU
1‑Sparsity Approximation Bounds for Packing Integer Programs.IPCO 2019Chandra Chekuri
Manuel R. Torres
 
Approximating Optimal Transport with Linear ProgramsSOSA 2019 SOSA
LP Relaxation and Tree Packings for Minimum k‑cutSOSA 2019Chandra Chekuri
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
Shalmoli Gupta
Bonn (video, slides)
Online Learning with Adversarial DelaysNIPS 2015Daniel KashabiNIPS

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

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

1‑Sparsity Approximation Bounds for Packing Integer Programs.

IPCO 2019

with Chandra Chekuri and Manuel R. Torres

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 Kashabi

slides: NIPS