2 papers
cs.DS2026
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…
cs.DS2025
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…