Parameterized approximation algorithms and lower bounds for \(k\)-center clustering and variants

DOI10.1007/S00453-024-01236-1MaRDI QIDQ6586660

Ramin Mousavi, Zachary Friggstad, Sayan Bandyapadhyay

Publication date: 13 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

hardnessparameterized algorithmsnon-uniform \(k\)-centerEuclidean \(k\)-center

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The planar \(k\)-means problem is NP-hard
• Clustering to minimize the maximum intercluster distance
• Exact and approximation algorithms for clustering
• Which problems have strongly exponential complexity?
• Reductions among high dimensional proximity problems
• Geometric clustering
• On the Complexity of Some Common Geometric Location Problems
• Extensions of Lipschitz mappings into a Hilbert space
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
• Parameterized Algorithms
• The Non-Uniform k -Center Problem
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• Tight lower bounds for approximate \& exact \(k\)-center in \(\mathbb{R}^d\)
• Johnson coverage hypothesis: inapproximability of \(k\)-means and \(k\)-median in \(\ell_p\)-metrics

This page was built for publication: Parameterized approximation algorithms and lower bounds for \(k\)-center clustering and variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6586660)