11 citations · 32 across the 20 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
A ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
Guy Kortsarz
The \emph{Tree Augmentation Problem (TAP)} is given a tree and additional set of {\em links} on , find such that is -edge-c…
cs.CC2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
cs.CC2013★ 4 cited
Fixed Parameter Inapproximability for Clique and SetCover in Time Super-exponential in OPT
Mohammad T. Hajiaghayi, Rohit Khandekar, Guy Kortsarz
In this paper, we consider proving inapproximability in terms of OPT and thus we base the foundations of fixed parameter inapproximability.