57 citations · 164 across the 38 of their papers we have counts for
39 papers
Constraint Satisfaction Problems with Advice
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max C…
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their…
Fair Representation Clustering with Several Protected Classes
Zhen Dai, Yury Makarychev, Ali Vakilian
We study the problem of fair -median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation -median pro…
Approximating Fair Clustering with Cascaded Norm Objectives
Eden Chlamtáč, Yury Makarychev, Ali Vakilian
We introduce the -Fair Clustering problem. In this problem, we are given a set of points and a collection of different weight functions . We would like to find a clus…
Local Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev +1
In the Correlation Clustering problem, we are given a complete weighted graph with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier. For a clusterin…
Correlation Clustering with Asymmetric Classification Errors
Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev +1
In the Correlation Clustering problem, we are given a weighted graph with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a cluste…