
Faster Algorithms for Rooted Connectivity in Directed Graphs
We consider the fundamental problems of determining the rooted and globa...
read it

Isolating Cuts, (Bi)Submodularity, and Faster Algorithms for Global Connectivity Problems
Li and Panigrahi, in recent work, obtained the first deterministic algor...
read it

Revisiting Priority kCenter: Fairness and Outliers
In the Priority kCenter problem, the input consists of a metric space (...
read it

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
We develop fast nearlinear time approximation algorithms for the minimu...
read it

Hypergraph kcut for fixed k in deterministic polynomial time
We consider the Hypergraphkcut problem. The input consists of a hyperg...
read it

Algorithms for Intersection Graphs of Multiple Intervals and Pseudo Disks
Intersection graphs of planar geometric objects such as intervals, disks...
read it

NodeWeighted Network Design in Planar and MinorClosed Families of Graphs
We consider nodeweighted survivable network design (SNDP) in planar gra...
read it

On Approximating Partial Set Cover and Generalizations
Partial Set Cover (PSC) is a generalization of the wellstudied Set Cove...
read it

ℓ_1sparsity Approximation Bounds for Packing Integer Programs
We consider approximation algorithms for packing integer programs (PIPs)...
read it

Parallelizing greedy for submodular set function maximization in matroids and beyond
We consider parallel, or low adaptivity, algorithms for submodular funct...
read it

LP Relaxation and Tree Packing for Minimum kcuts
Karger used spanning tree packings to derive a near lineartime randomiz...
read it

On Approximating (Sparse) Covering Integer Programs
We consider approximation algorithms for covering integer programs of th...
read it

Submodular Function Maximization in Parallel via the Multilinear Relaxation
Balkanski and Singer [5] recently initiated the study of adaptivity (or ...
read it

Perturbation Resilient Clustering for kCenter and Related Problems via LP Relaxations
We consider clustering in the perturbation resilience model that has bee...
read it

Fast Approximations for MetricTSP via Linear Programming
We develop faster approximation algorithms for MetricTSP building on re...
read it
Chandra Chekuri
is this you? claim profile