14 citations · 51 across the 29 of their papers we have counts for
Showing 2021 · cs.CCShow all
2 papers · 2 filters
cs.CC2021
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…
cs.CC2021★ 1 cited
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…