Chris Schwiegelshohn

activity

20242026

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2026

A $(2 + ε)$ -Approximation Algorithm for Metric $k$ -Median

Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +2

In the classical NP-hard metric $k$ -median problem, we are given a set of $n$ clients and centers with metric distances between them, along with an integer parameter $k \geq 1$ . The…

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 $C$ and a set of facilities $F$ in a metric space $(C \…

cs.DS2025

On Approximability of $ℓ_{2}^{2}$ Min-Sum Clustering

Karthik C. S., Euiwoong Lee, Yuval Rabani +2

The $ℓ_{2}^{2}$ min-sum $k$ -clustering problem is to partition an input set into clusters $C_{1}, \dots, C_{k}$ to minimize $\sum_{i = 1}^{k} \sum_{p, q \in C_{i}} ∥ p - q ∥_{2}^{2}$ . Although $\ell_2^2…

cs.DS2024

Sensitivity Sampling for $k$ -Means: Worst Case and Stability Optimal Coreset Bounds

Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu +2

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as $k$ -means. Given a point set $P$ , a coreset $I^c ◯$ is a small, weighted sum…

A (2+ε)-Approximation Algorithm for Metric k-Median

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median

On Approximability of ℓ22​ Min-Sum Clustering

Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds

A $(2 + ε)$ -Approximation Algorithm for Metric $k$ -Median

On Approximability of $ℓ_{2}^{2}$ Min-Sum Clustering

Sensitivity Sampling for $k$ -Means: Worst Case and Stability Optimal Coreset Bounds