43 citations · 181 across the 50 of their papers we have counts for
4 papers · 2 filters
Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
Given a metric space on n points, an α-approximate universal algorithm for the Steiner tree problem outputs a distribution over rooted spanning trees such that for any subset X of…
Approximability of Capacitated Network Design
Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna +1
In the {\em capacitated} survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minim…
Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems
Deeparnab Chakrabarty, Chaitanya Swamy
We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients…
On Column-restricted and Priority Covering Integer Programs
Deeparnab Chakrabarty, Elyot Grant, Jochen Koenemann
In a column-restricted covering integer program (CCIP), all the non-zero entries of any column of the constraint matrix are equal. Such programs capture capacitated versions of cov…