16 citations · 59 across the 25 of their papers we have counts for
33 papers
A Note on Approximability of Densest At-Least-k-Subgraph
Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi
We study the Densest At-Least--Subgraph (DALS) problem, in which we are given an undirected graph and an integer , and the goal is to find a subgraph of with at le…
On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
Bundit Laekhanukit
The Directed Steiner Tree (DST) problem is defined on a directed graph , where we are given a designated root vertex and a set of terminals $K \subseteq V \setminu…
Simple Combinatorial Construction of the -Lower Bound for Approximating the Parameterized -Clique
Yijia Chen, Yi Feng, Bundit Laekhanukit +1
In the parameterized -clique problem, or -Clique for short, we are given a graph and a parameter . The goal is to decide whether there exist vertices in t…
Survivable Network Design Revisited: Group-Connectivity
Qingyun Chen, Bundit Laekhanukit, Chao Liao +1
In the classical survivable network design problem (SNDP), we are given an undirected graph with costs on edges and a connectivity requirement for each pair of v…
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
Chao Liao, Qingyun Chen, Bundit Laekhanukit +1
In the -connected directed Steiner tree problem (-DST), we are given an -vertex directed graph with edge costs, a connectivity requirement , a root a…
On a Partition LP Relaxation for Min-Cost 2-Node Connected Spanning Subgraphs
Logan Grout, Joseph Cheriyan, Bundit Laekhanukit
Our motivation is to improve on the best approximation guarantee known for the problem of finding a minimum-cost 2-node connected spanning subgraph of a given undirected graph with…