13 citations · 24 across the 8 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012★ 13 cited
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…
math.CO2012★ 1 cited
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…