3 citations · 5 across the 4 of their papers we have counts for
11 papers
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
We show that Set Cover on instances with elements cannot be approximated within -factor in time exp(, for any and any , assuming the Expo…
Bounded Degree Group Steiner Tree Problems
Guy Kortsarz, Zeev Nutov
We study two problems that seek a subtree of a graph such that satisfies a certain property and has minimal maximum degree. - In the Min-Degree Group Steiner Tree…
On Approximating Degree-Bounded Network Design Problems
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit +3
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph with edge costs $c \in \mathbb{R}…
On subexponential running times for approximating directed Steiner tree and related problems
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, le…
Spanning Trees With Edge Conflicts and Wireless Connectivity
Magnus M. Halldorsson, Guy Kortsarz, Pradipta Mitra +1
We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility.…
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…