14 citations · 51 across the 29 of their papers we have counts for
5 papers · 1 filter
Strong Hardness of Approximation for Tree Transversals
Euiwoong Lee, Pengxiang Wang
Let be a fixed graph. The -Transversal problem, given a graph , asks to remove the smallest number of vertices from so that does not contain as a subgraph. Wh…
On Some Variants of Euclidean K-Supplier
Euiwoong Lee, Viswanath Nagarajan, Lily Wang
The -Supplier problem is an important location problem that has been actively studied in both general and Euclidean metrics. Many of its variants have also been studied, primari…
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
K-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, parti…
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…
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…