11 citations · 32 across the 20 of their papers we have counts for
4 papers · 1 filter
Low-Risk Mechanisms for the Kidney Exchange Game
Hossein Esfandiari, Guy Kortsarz
In this paper we consider the pairwise kidney exchange game. This game naturally appears in situations that some service providers benefit from pairwise allocations on a network, s…
A LP approximation for the Tree Augmentation Problem
Guy Kortsarz, Zeev Nutov
In the Tree Augmentation Problem (TAP) the goal is to augment a tree by a minimum size edge set from a given edge set such that is -edge-connected. The be…
A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Guy Kortsarz, Zeev Nutov
The Tree Augmentation Problem (TAP) is: given a connected graph and an edge set on find a minimum size subset of edges such that $(V,{\cal…
Approximation Algorithms for Connected Maximum Cut and Related Problems
MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid +2
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S V that maximizes the number o…