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…
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Eden Chlamtáč, Michael Dinitz, Guy Kortsarz +1
It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), dist…
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…
Everywhere-Sparse Spanners via Dense Subgraphs
Eden Chlamtac, Michael Dinitz, Robert Krauthgamer
The significant progress in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped spanners that are everywhere-sparse (small m…
Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods
Eden Chlamtac, Zac Friggstad, Konstantinos Georgiou
Recently, Cygan, Kowalik, and Wykurz [IPL 2009] gave sub-exponential-time approximation algorithms for the Set-Cover problem with approximation ratios better than ln(n). In light o…
Linear Index Coding via Semidefinite Programming
Eden Chlamtac, Ishay Haviv
In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n bit word to n receivers (one bit per receiver), where the receivers have side…
Inapproximability of NP-Complete Variants of Nash Equilibrium
Per Austrin, Mark Braverman, Eden Chlamtac
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as f…
Approximating Sparsest Cut in Graphs of Bounded Treewidth
Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
We give the first constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the f…