3 papers
cs.DS2026
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +1
The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients and a set of facilities in a metric space $(C \…
cs.DS2025
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…
cs.DS2025
A Constant-factor Approximation for Weighted Bond Cover
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
The Weighted -Vertex Deletion for a class of graphs asks, weighted graph , for a minimum weight vertex set such that The case when…