13 citations · 24 across the 8 of their papers we have counts for
13 papers
An -Approximation for Steiner -Forest
Eden Chlamtáč
We give an -approximation algorithm for the Steiner -Forest problem, for any constant . As a function of , this improves over the $O(\min\…
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
Eden Chlamtáč, Yury Makarychev, Ali Vakilian
We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves…
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…
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
Eden Chlamtáč, Michael Dinitz, Yury Makarychev
In the Minimum k-Union problem (MkU) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural…