krq (at) purdue.eduMy 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.
Fall 2022: Randomized Algorithms
Spring 2022: Undergraduate Algorithms
Fall 2021: Advanced Topics in Algorithms
Spring 2021: Graduate Algorithms
Fall 2020: Randomized Algorithms
Spring 2020: Graduate Algorithms
Fall 2019: Randomized Algorithms (with Petros Drineas)
My research is supported in part by NSF. See DBLP for a more up-to-date list.
Circle Packing of Planar Graphs in Nearly Linear Time
with Sally Dong and Yin Tat Lee
Fast LP-based Approximations for Geometric Packing and Covering Problems
with Chandra Chekuri and Sariel Har-Peled
Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond
with Chandra Chekuri
ℓ1‑Sparsity Approximation Bounds for Packing Integer Programs.
with Chandra Chekuri and Manuel R. Torres
LP Relaxation and Tree Packings for Minimum k‑cut
with Chandra Chekuri and Chao Xu
On Approximating (Sparse) Covering Integer Programs
with Chandra Chekuri
Submodular Function Maximization in Parallel via the Multilinear Relaxation
with Chandra Chekuri
Fast Approximations for Metric‑TSP via Linear Programming
arXiv 2018
with Chandra Chekuri
Randomized MWU for Positive LPs
with Chandra Chekuri
Approximation Algorithms for Polynomial Expansion and Low‑Density Graphs
SIAM J. Comput. (SICOMP)
2017
ESA
2015
with Sariel Har-Peled
Approximating the Held‑Karp Bound for Metric TSP in Nearly Linear Time
with Chandra Chekuri
Near‑Linear‑Time Approximation Schemes for some Implicit Fractional Packing Problems
with Chandra Chekuri
A Fast Approximation for Maximum Weight Matroid Intersection
with Chandra Chekuri
Streaming Algorithms for Submodular Function Maximization
with Chandra Chekuri and Shalmoli Gupta
Online Learning with Adversarial Delays
with Daniel Kashabi