11 citations · 32 across the 20 of their papers we have counts for
27 papers
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…
Approximations and Hardness of Packing Partially Ordered Items
Ilan Doron-Arad, Guy Kortsarz, Joseph Naor +2
Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (CPO). Given a capacity…
Improved Approximations for Relative Survivable Network Design
Michael Dinitz, Ama Koranteng, Guy Kortsarz +1
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum -Edge-Connected Sp…
Degrees and Network Design: New Problems and Approximations
Michael Dinitz, Guy Kortsarz, Shi Li
While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an obje…
Relative Survivable Network Design
Michael Dinitz, Ama Koranteng, Guy Kortsarz
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum -Edge-Connected Sp…
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…
Improved approximation algorithm for the Dense-3-Subhypergraph Problem
Amey Bhangale, Rajiv Gandhi, Guy Kortsarz
The study of Dense--Subhypergraph problem was initiated in Chlamt{á}c et al. [Approx'16]. The input is a universe and collection of subsets of , each of size $…
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Eden Chlamtáč, Michael Dinitz, Guy Kortsarz +1
It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), dist…
The Densest k-Subhypergraph Problem
Eden Chlamtáč, Michael Dinitz, Christian Konrad +2
The Densest -Subgraph (DS) problem, and its corresponding minimization problem Smallest -Edge Subgraph (SES), have come to play a central role in approximation algorith…
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…
Edge covering with budget constrains
Rajiv Gandhi, G. Kortsarz
We study two related problems: finding a set of k vertices and minimum number of edges (kmin) and finding a graph with at least m' edges and minimum number of vertices (mvms). Gold…
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.
Fixed-Parameter and Approximation Algorithms: A New Look
Rajesh Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz
A Fixed-Parameter Tractable (\FPT) -approximation algorithm for a minimization (resp. maximization) parameterized problem is an FPT algorithm that, given an instance $(x, k)…
Approximation Algorithms for Movement Repairmen
MohammadTaghi Hajiaghayi, Rohit Khandekar, M. Reza Khani +1
In the {\em Movement Repairmen (MR)} problem we are given a metric space along with a set of repairmen with their start depots $s_1, s_2, ...,…
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…
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…