6 papers · 1 filter
Packing Compact Subgraphs with Applications to Districting
Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte +3
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e…
The Price of Privacy For Approximating Max-CSP
Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3
We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…
Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H. -C. Jiang +4
We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak or…
Hardness and Approximation Algorithms for Balanced Districting Problems
Prathamesh Dharangutte, Jie Gao, Shang-En Huang +1
We introduce and study the problem of balanced districting, where given an undirected graph with vertices carrying two types of weights (different population, resource types, etc)…
Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai +2
We study the dynamic correlation clustering problem with edge label flips. In correlation clustering, we are given a -vertex complete graph whose edges are l…
Dynamic Trace Estimation
Prathamesh Dharangutte, Christopher Musco
We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our…