4 papers · 1 filter
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…
The Norms of Graph Spanners
Eden Chlamtáč, Michael Dinitz, Thomas Robinson
A -spanner of a graph is a subgraph in which all distances are preserved up to a multiplicative factor. A classical result of Althöfer et al. is that for every integ…
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
Eden Chlamtáč, Pasin Manurangsi
The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest--Su…
The Densest k-Subhypergraph Problem
Eden Chlamtáč, Michael Dinitz, Christian Konrad +2
The Densest -Subgraph (DS) problem, and its corresponding minimization problem Smallest -Edge Subgraph (SES), have come to play a central role in approximation algorith…