We present a new technique for efficiently removing almost all short cycles in a graph
without unintentionally removing its triangles. Consequently, triangle finding problems do …

Parameterization and approximation are two popular ways of coping with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

We prove conditional near-quadratic running time lower bounds for approximate
Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically …

We investigate the fine-grained complexity of approximating the classical $ k $-median/$ k $-
means clustering problems in general metric spaces. We show how to improve the …

We consider questions that arise from the intersection between the areas of approximation
algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The …

Abstract k-means and k-median clustering are powerful unsupervised machine learning
techniques. However, due to complicated dependencies on all the features, it is challenging …

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 …

We study the parameterized complexity of various classic vertex-deletion problems such as
Odd cycle transversal, Vertex planarization, and Chordal vertex deletion under hybrid …

The k-means objective is arguably the most widely-used cost function for modeling
clustering tasks in a metric space. In practice and historically, k-means is thought of in a …

Proving hardness of approximation for min-sum objectives is an infamous challenge. For
classic problems such as the Traveling Salesman problem, the Steiner tree problem, or the k …