Image de couverture de livre

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

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Cohen-Addad, Vincent, Grandoni, Fabrizio, Lee, Euiwoong, Schwiegelshohn, Chris, Svensson, Ola
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2022)

An Improved Greedy Approximation for (Metric) $k$-Means
par: Charikar, Moses, et autres
Publié: (2026)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
par: Bansal, Nikhil, et autres
Publié: (2024)

Separating $k$-Median from the Supplier Version
par: Anand, Aditya, et autres
Publié: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
par: Lee, Euiwoong, et autres
Publié: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
par: S., Karthik C., et autres
Publié: (2024)

Retriever Portfolios: A Principled Approach to Adaptive RAG
par: Stouras, Miltiadis, et autres
Publié: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
par: Armbruster, Alexander, et autres
Publié: (2026)

Understanding the Cluster LP for Correlation Clustering
par: Cao, Nairen, et autres
Publié: (2024)

On Approximability of $\ell_2^2$ Min-Sum Clustering
par: S., Karthik C., et autres
Publié: (2024)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
par: Fan, Chenglin, et autres
Publié: (2025)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
par: Anand, Aditya, et autres
Publié: (2025)

Distributed Algorithms for Euclidean Clustering
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
par: Lee, Dahoon, et autres
Publié: (2025)

Max-Cut with $ε$-Accurate Predictions
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

Simple and Optimal Sublinear Algorithms for Mean Estimation
par: Bertolotti, Beatrice, et autres
Publié: (2024)

Correlation Clustering Beyond the Pivot Algorithm
par: Behnezhad, Soheil, et autres
Publié: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
par: Grandoni, Fabrizio, et autres
Publié: (2026)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
par: Eberle, Franziska, et autres
Publié: (2024)

Approximating Small Sparse Cuts
par: Anand, Aditya, et autres
Publié: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
par: Bansal, Nikhil, et autres
Publié: (2026)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
par: Beretta, Lorenzo, et autres
Publié: (2025)

Solving the Correlation Cluster LP in Sublinear Time
par: Cao, Nairen, et autres
Publié: (2025)

Static to Dynamic Correlation Clustering
par: Cao, Nairen, et autres
Publié: (2025)

A PTAS for Weighted Triangle-free 2-Matching
par: Bosch-Calvo, Miguel, et autres
Publié: (2026)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

Unsplittable Flow on a Short Path
par: Doron-Arad, Ilan, et autres
Publié: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

Facility Location on High-dimensional Euclidean Spaces
par: Lee, Euiwoong, et autres
Publié: (2025)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
par: Byrka, Jarosław, et autres
Publié: (2024)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
par: Bakshi, Ainesh, et autres
Publié: (2023)

Combinatorial Optimization using Comparison Oracles
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
par: Ghoshal, Suprovat, et autres
Publié: (2026)