11 citations · 32 across the 20 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DS2012
Approximating Source Location and Star Survivable Network Problems
Guy Kortsarz, Zeev Nutov
In Source Location (SL) problems the goal is to select a mini-mum cost source set such that the connectivity (or flow) from to any node is at least…
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★ 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…