research
∙
04/15/2023
Simple Combinatorial Construction of the k^o(1)-Lower Bound for Approximating the Parameterized k-Clique
In the parameterized k-clique problem, or k-Clique for short, we are giv...
share
research
∙
04/28/2022
Survivable Network Design Revisited: Group-Connectivity
In the classical survivable network design problem (SNDP), we are given ...
research
∙
02/26/2022
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
In the k-connected directed Steiner tree problem (k-DST), we are given a...
research
∙
11/15/2021
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs
Our motivation is to improve on the best approximation guarantee known f...
research
∙
10/26/2021
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
In the Directed Steiner Tree (DST) problem, we are given a directed grap...
research
∙
08/27/2020
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
We study the variant of the Euclidean Traveling Salesman problem where i...
research
∙
07/15/2020
Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic information-theoretic and...
research
∙
11/20/2019
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a...
research
∙
10/23/2019
Mimicking Networks Parameterized by Connectivity
Given a graph G=(V,E), capacities w(e) on edges, and a subset of termina...
research
∙
07/26/2019
Tight Approximation for Variants of Directed Steiner Tree via State-Tree Decomposition and Linear Programming Rounding
Directed Steiner Tree (DST) is a central problem in combinatorial optimi...
research
∙
11/07/2018
O(^2k/k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
In the Directed Steiner Tree (DST) problem we are given an n-vertex dire...
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
∙
02/28/2018
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)...
research
∙
11/29/2017
On the Parameterized Complexity of Approximating Dominating Set
We study the parameterized complexity of approximating the k-Dominating ...
research
∙
08/14/2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
research
∙
08/11/2017