Image de couverture de livre

Near-Optimal Bounds for Parameterized Euclidean k-means

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Cohen-Addad, Vincent, S., Karthik C., Saulpic, David, Schwiegelshohn, Chris
Format:	Preprint
Publié:	2026
Sujets:	Computational Geometry Computational Complexity 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

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

On connections between k-coloring and Euclidean k-means
par: Aman, Enver, et autres
Publié: (2024)

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

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

Fine-Grained Complexity of Continuous Euclidean k-Center
par: Blank, Lotte, et autres
Publié: (2026)

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

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

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

On Approximability of Steiner Tree in $\ell_p$-metrics
par: Fleischmann, Henry, et autres
Publié: (2023)

Hardness of Median and Center in the Ulam Metric
par: Fischer, Nick, et autres
Publié: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
par: Fleischmann, Henry, et autres
Publié: (2023)

Recognizing 2-Layer and Outer $k$-Planar Graphs
par: Kobayashi, Yasuaki, et autres
Publié: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
par: Bringmann, Karl, et autres
Publié: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
par: Mao, Songtao
Publié: (2026)

Structural Parameterizations for Two Bounded Degree Problems Revisited
par: Lampis, Michael, et autres
Publié: (2023)

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

Computational Complexities of Folding
par: Eppstein, David
Publié: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
par: Xun, Zhiyang, et autres
Publié: (2024)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
par: Maalouly, Nicolas El, et autres
Publié: (2025)

Impossibility of Depth Reduction in Explainable Clustering
par: Deng, Chengyuan, et autres
Publié: (2023)

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

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
par: Huang, Lingxiao, et autres
Publié: (2022)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
par: Krivošija, Amer, et autres
Publié: (2025)

Beyond Bits: An Introduction to Computation over the Reals
par: Miltzow, Tillmann
Publié: (2026)

Fast and simple multiplication of bounded twin-width matrices
par: Kozma, László, et autres
Publié: (2026)

Approximate Algorithms for Chamfer Distance Under Translation
par: Halevi, Gil, et autres
Publié: (2026)

Universal Solvability for Robot Motion Planning on Graphs
par: Dhar, Anubhav, et autres
Publié: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
par: Ray, Arka, et autres
Publié: (2023)

Subcoloring of (Unit) Disk Graphs
par: Marin, Malory, et autres
Publié: (2025)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
par: Goodrich, Michael T., et autres
Publié: (2024)

On Approximating the Dynamic and Discrete Network Flow Problem
par: Manna, Bubai, et autres
Publié: (2024)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
par: Bharathi, Arpitha P., et autres
Publié: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
par: Minzer, Dor, et autres
Publié: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Near-Optimality for Single-Source Personalized PageRank
par: Jiang, Xinpeng, et autres
Publié: (2025)

Parameterized Complexity of Vehicle Routing
par: Döring, Michelle, et autres
Publié: (2025)

Parameterized Vertex Integrity Revisited
par: Hanaka, Tesshu, et autres
Publié: (2024)