43 citations · 181 across the 50 of their papers we have counts for
6 papers · 1 filter
The Heterogeneous Capacitated -Center Problem
Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar
In this paper we initiate the study of the heterogeneous capacitated -center problem: given a metric space , and a collection of capacities. The goal is to op…
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in Amortized Update Time
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletion…
Subquadratic Submodular Function Minimization
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +1
Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be sol…
A Non-Adaptive Tester for Unateness
Deeparnab Chakrabarty, C. Seshadhri
Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, -query tester for unateness of Boolean functions . In this note we…
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy
In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space and a collection of balls of radii ,…
Graph Balancing with Two Edge Types
Deeparnab Chakrabarty, Kirankumar Shiragur
In the graph balancing problem the goal is to orient a weighted undirected graph to minimize the maximum weighted in-degree. This special case of makespan minimization is NP-hard t…