research
∙
04/13/2023
Improved Approximations for Relative Survivable Network Design
One of the most important and well-studied settings for network design i...
share
research
∙
02/22/2023
Degrees and Network Design: New Problems and Approximations
While much of network design focuses mostly on cost (number or weight of...
research
∙
06/24/2022
Relative Survivable Network Design
One of the most important and well-studied settings for network design i...
research
∙
08/12/2020
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
We show that Set Cover on instances with N elements cannot be approximat...
research
∙
10/28/2019
Bounded Degree Group Steiner Tree Problems
We study two problems that seek a subtree T of a graph G=(V,E) such that...
research
∙
11/02/2018
On subexponential running times for approximating directed Steiner tree and related problems
This paper concerns proving almost tight (super-polynomial) running time...
research
∙
03/12/2018
Spanning Trees With Edge Conflicts and Wireless Connectivity
We introduce the problem of finding a spanning tree along with a partiti...
research
∙
08/14/2017