Imagen de Portada

On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dai, Han, Li, Shi, Peng, Sijin
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

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
por: Zhou, Jianqi, et al.
Publicado: (2025)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
por: Rohwedder, Lars
Publicado: (2025)

FPT Approximations for Fair $k$-Min-Sum-Radii
por: Carta, Lena, et al.
Publicado: (2024)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
por: Jansen, Bart M. P., et al.
Publicado: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
por: Eisenbrand, Friedrich, et al.
Publicado: (2024)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
por: Chen, Lin, et al.
Publicado: (2026)

FPT Approximations for Connected Maximum Coverage
por: Inamdar, Tanmay, et al.
Publicado: (2026)

FPT Approximation for Capacitated Sum of Radii
por: Jaiswal, Ragesh, et al.
Publicado: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
por: Norose, Ryoma, et al.
Publicado: (2024)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
por: Krithika, R., et al.
Publicado: (2025)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
por: Manurangsi, Pasin
Publicado: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
por: Murakami, Hitoshi, et al.
Publicado: (2024)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
por: Bandyapadhyay, Sayan, et al.
Publicado: (2023)

Optimal FPT-Approximability for Modular Linear Equations
por: Dabrowski, Konrad K., et al.
Publicado: (2026)

Improved FPT Approximation for Non-metric TSP
por: Bampis, Evripidis, et al.
Publicado: (2024)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
por: Liu, Shuilian, et al.
Publicado: (2025)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
por: Lanzinger, Matthias, et al.
Publicado: (2023)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
por: Chen, Yong, et al.
Publicado: (2025)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
por: Grandoni, Fabrizio, et al.
Publicado: (2026)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
por: Gadekar, Ameet
Publicado: (2026)

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

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
por: Das, Rathish, et al.
Publicado: (2025)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
por: Jansen, Klaus, et al.
Publicado: (2024)

Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
por: Habib, Ruhan, et al.
Publicado: (2025)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
por: Fischer, Nick, et al.
Publicado: (2026)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
por: Eberle, Franziska, et al.
Publicado: (2024)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
por: Cervenjak, Philip, et al.
Publicado: (2024)

Logarithmic Approximations for Fair k-Set Selection
por: Li, Shi, et al.
Publicado: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
por: Filtser, Arnold, et al.
Publicado: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
por: Swartworth, William, et al.
Publicado: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
por: Mömke, Tobias, et al.
Publicado: (2024)

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

An FPT algorithm for Matching Cut and d-cut
por: Aravind, N R, et al.
Publicado: (2021)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
por: Geng, Yutong, et al.
Publicado: (2025)

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

Hardness and Approximation Algorithms for Balanced Districting Problems
por: Dharangutte, Prathamesh, et al.
Publicado: (2025)

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

Hardness and Tight Approximations of Demand Strip Packing
por: Jansen, Klaus, et al.
Publicado: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
por: Madani, Amirali, et al.
Publicado: (2025)

$k$-Clustering via Iterative Randomized Rounding
por: Byrka, Jarosław, et al.
Publicado: (2026)