16 citations · 59 across the 25 of their papers we have counts for
24 papers · 1 filter
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…
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…
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
Shi Li, Bundit Laekhanukit
In the Directed Steiner Tree (DST) problem, we are given a directed graph on vertices with edge-costs , a root vertex , and a se…
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit +1
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour t…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei +1
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G=(V, E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connect…
Mimicking Networks Parameterized by Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +1
Given a graph , capacities on edges, and a subset of terminals , a mimicking network for is a graph $(…
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}…
-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
In the Directed Steiner Tree (DST) problem we are given an -vertex directed edge-weighted graph, a root , and a collection of terminal nodes. Our goal is to find a minimu…
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…
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
Parinya Chalermsook, Syamantak Das, Guy Even +2
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph on vertices, a root vertex and a collection of groups $\{S_i\}_{i\in[h]}:…
New Tools and Connections for Exponential-time Approximation
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit +2
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter , and the goal is to d…
Finding All Useless Arcs in Directed Planar Graphs
Jittat Fakcharoenphol, Bundit Laekhanukit, Pattara Sukprasert
We present a linear-time algorithm for simplifying flow networks on directed planar graphs: Given a directed planar graph on vertices, a source vertex and a sink vertex …
Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree
Fabrizio Grandoni, Bundit Laekhanukit
In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an -vertex weighted directed graph, a root ,…
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…
Approximating Directed Steiner Problems via Tree Embedding
Bundit Laekhanukit
In the k-edge connected directed Steiner tree (k-DST) problem, we are given a directed graph G on n vertices with edge-costs, a root vertex r, a set of h terminals T and an integer…
Routing Regardless of Network Stability
Bundit Laekhanukit, Adrian Vetta, Gordon Wilfong
We examine the effectiveness of packet routing in this model for the broad class next-hop preferences with filtering. Here each node v has a filtering list D(v) consisting of nodes…
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc dis…
An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem
Bundit Laekhanukit
The minimum-cost subset -connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a…
Faster Algorithms for Semi-Matching Problems
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
We consider the problem of finding \textit{semi-matching} in bipartite graphs which is also extensively studied under various names in the scheduling literature. We give faster alg…
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
Patrick Briest, Sanjeev Khanna
We consider the Stackelberg shortest-path pricing problem, which is defined as follows. Given a graph G with fixed-cost and pricable edges and two distinct vertices s and t, we may…