29 citations · 80 across the 30 of their papers we have counts for
Showing 2012 · cs.DSShow all
3 papers · 2 filters
cs.DS2012
Matroid Secretary for Regular and Decomposable Matroids
Michael Dinitz, Guy Kortsarz
In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent…
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…
cs.DS2012★ 1 cited
Label Cover instances with large girth and the hardness of approximating basic k-spanner
Michael Dinitz, Guy Kortsarz, Ran Raz
We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some , the problem is roughly…