Buchumschlag

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	la Tour, Max Dupré, Saulpic, David
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Artificial Intelligence
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Making Old Things New: A Unified Algorithm for Differentially Private Clustering
von: la Tour, Max Dupré, et al.
Veröffentlicht: (2024)

Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
von: Nguyen, Hue T., et al.
Veröffentlicht: (2025)

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
von: Luo, Chunyu, et al.
Veröffentlicht: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Gerrymandering Planar Graphs
von: Dippel, Jack, et al.
Veröffentlicht: (2023)

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Faster Combinatorial k-Clique Algorithms
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

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

Separating $k$-Median from the Supplier Version
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Facility Location and $k$-Median with Fair Outliers
von: Dabas, Rajni, et al.
Veröffentlicht: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
von: Filtser, Arnold, et al.
Veröffentlicht: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

A Faster $k$-means++ Algorithm
von: Liang, Jiehao, et al.
Veröffentlicht: (2022)

3SUM in Preprocessed Universes: Faster and Simpler
von: Kasliwal, Shashwat, et al.
Veröffentlicht: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
von: Costa, Martín, et al.
Veröffentlicht: (2025)

Connected k-Median with Disjoint and Non-disjoint Clusters
von: Eube, Jan, et al.
Veröffentlicht: (2025)

Compatibility of Max and Sum Objectives for Committee Selection and $k$-Facility Location
von: Han, Yue, et al.
Veröffentlicht: (2025)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
von: Funk, Nicole, et al.
Veröffentlicht: (2026)

Faster and Simpler Online Computation of String Net Frequency
von: Inenaga, Shunsuke
Veröffentlicht: (2024)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
von: Qi, Chuhan
Veröffentlicht: (2025)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
von: Cáceres, Manuel, et al.
Veröffentlicht: (2025)

Faster ED-String Matching with $k$ Mismatches
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search
von: Shimoda, Takumi, et al.
Veröffentlicht: (2024)

Mini-Batch Kernel $k$-means
von: Jourdan, Ben, et al.
Veröffentlicht: (2024)

Node-Weighted Triangles: Faster and Simpler
von: Akmal, Shyan, et al.
Veröffentlicht: (2026)

Faster two-dimensional pattern matching with $k$ mismatches
von: Ellert, Jonas, et al.
Veröffentlicht: (2024)

Faster algorithms for k-Orthogonal Vectors in low dimension
von: Dürr, Anita, et al.
Veröffentlicht: (2025)

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

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

Average Sensitivity of Hierarchical $k$-Median Clustering
von: Li, Shijie, et al.
Veröffentlicht: (2025)

OpenTensor: Reproducing Faster Matrix Multiplication Discovering Algorithms
von: Sun, Yiwen, et al.
Veröffentlicht: (2024)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)