Dept. of Computer Science, Purdue University

`krq (at) purdue.edu`

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 teaching graduate algorithms (CS580).

Last semester I co-taught randomized algorithms (CS590-RA) with Petros Drineas.

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