11 citations · 32 across the 20 of their papers we have counts for
22 papers · 1 filter
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…
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…
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 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…
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…
Steiner Forest Orientation Problems
Marek Cygan, Guy Kortsarz, Zeev Nutov
We consider connectivity problems with orientation constraints. Given a directed graph and a collection of ordered node pairs let $P[D]=\{(u,v) \in P: D {contains a} uv{-pa…
Combinatorial Algorithms for Capacitated Network Design
MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz +1
We focus on designing combinatorial algorithms for the Capacitated Network Design problem (Cap-SNDP). The Cap-SNDP is the problem of satisfying connectivity requirements when edges…