Cover Image

Deterministic $k$-Median Clustering in Near-Optimal Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Costa, Martín, Farokhnejad, Ermiya
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Connected k-Median with Disjoint and Non-disjoint Clusters
by: Eube, Jan, et al.
Published: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Average Sensitivity of Hierarchical $k$-Median Clustering
by: Li, Shijie, et al.
Published: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
by: Grilnberger, Mara, et al.
Published: (2026)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Facility Location and $k$-Median with Fair Outliers
by: Dabas, Rajni, et al.
Published: (2025)

Separating $k$-Median from the Supplier Version
by: Anand, Aditya, et al.
Published: (2024)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
by: Cheng, Kangke, et al.
Published: (2026)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Private Geometric Median in Nearly-Linear Time
by: Kumar, Syamantak, et al.
Published: (2025)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
by: Harada, Tsubasa, et al.
Published: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

Deterministic Mincut in Almost-Linear Time
by: Li, Jason
Published: (2021)

Robust-Sorting and Applications to Ulam-Median
by: Jaiswal, Ragesh, et al.
Published: (2025)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)