Imagen de Portada

Faster Approximation Algorithms for k-Center via Data Reduction

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Filtser, Arnold, Jiang, Shaofeng H. -C., Li, Yi, Naredla, Anurag Murty, Psarros, Ioannis, Yang, Qiaoyuan, Zhang, Qin
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Moderate Dimension Reduction for $k$-Center Clustering
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2023)

The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics
por: Nikoleit, Henri, et al.
Publicado: (2026)

Fully Dynamic Algorithms for Chamfer Distance
por: Goranci, Gramoz, et al.
Publicado: (2025)

Stochastic Embedding of Digraphs into DAGs
por: Filtser, Arnold
Publicado: (2025)

Scattering and Sparse Partitions, and their Applications
por: Filtser, Arnold
Publicado: (2020)

Hop-Constrained Metric Embeddings and their Applications
por: Filtser, Arnold
Publicado: (2021)

A face cover perspective to $\ell_1$ embeddings of planar graphs
por: Filtser, Arnold
Publicado: (2019)

On Strong Diameter Padded Decompositions
por: Filtser, Arnold
Publicado: (2019)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
por: Driemel, Anne, et al.
Publicado: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
por: Filtser, Arnold, et al.
Publicado: (2024)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
por: Conroy, Jonathan, et al.
Publicado: (2025)

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

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
por: Filtser, Arnold
Publicado: (2024)

Highway Dimension: a Metric View
por: Feldmann, Andreas Emil, et al.
Publicado: (2024)

Fair Clustering in the Sliding Window Model
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2025)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2025)

Faster Combinatorial k-Clique Algorithms
por: Abboud, Amir, et al.
Publicado: (2024)

Fully Scalable MPC Algorithms for Euclidean k-Center
por: Czumaj, Artur, et al.
Publicado: (2025)

Faster Algorithms for Schatten-p Low Rank Approximation
por: Kacham, Praneeth, et al.
Publicado: (2024)

Dynamic Light Spanners in Doubling Metrics
por: Bhore, Sujoy, et al.
Publicado: (2026)

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
por: Filtser, Arnold, et al.
Publicado: (2026)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
por: Kadria, Avi, et al.
Publicado: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
por: Łącki, Jakub, et al.
Publicado: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
por: Ashvinkumar, Vikrant, et al.
Publicado: (2024)

Round-efficient Fully-scalable MPC algorithms for k-Means
por: Jiang, Shaofeng H. -C., et al.
Publicado: (2026)

Visibility Queries in Simple Polygons
por: Bhore, Sujoy, et al.
Publicado: (2026)

Near-Optimal Dimension Reduction for Facility Location
por: Huang, Lingxiao, et al.
Publicado: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
por: van Wijland, Ernest, et al.
Publicado: (2023)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
por: Bhore, Sujoy, et al.
Publicado: (2023)

A Faster $k$-means++ Algorithm
por: Liang, Jiehao, et al.
Publicado: (2022)

Streaming Algorithms for Geometric Steiner Forest
por: Czumaj, Artur, et al.
Publicado: (2020)

A Faster Deterministic Approximation Algorithm for TTP-2
por: Kanaya, Yuga, et al.
Publicado: (2023)

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

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
por: Luo, Chunyu, et al.
Publicado: (2024)

A Query-Driven Approach to Space-Efficient Range Searching
por: Fotakis, Dimitris, et al.
Publicado: (2025)

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

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
por: Esmer, Barış Can, et al.
Publicado: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
por: Ebbens, Matthijs, et al.
Publicado: (2024)

Faster Algorithm for Structured John Ellipsoid Computation
por: Cao, Yang, et al.
Publicado: (2022)