27 citations · 41 across the 8 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.CC2021
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Karthik C. S., Subhash Khot
The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique problem where an in…
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…