Parameterized complexity of categorical clustering with size constraints

DOI10.1007/978-3-030-83508-8_28OpenAlexW3197924520MaRDI QIDQ832880

Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2104.07974

zbMATH Keywords

parameterized complexitycapacitated clusteringcategorical clustering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Related Items (1)

Lossy kernelization of same-size clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid and knapsack center problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• Parameterized low-rank binary matrix approximation
• Parameterized \(k\)-clustering: tractability island
• The complexity of the single individual SNP haplotyping problem
• The number of trees
• Achieving anonymity via clustering
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Closest Substring Problems with Small Distances
• Color-coding
• Kernelization
• Constant Time Generation of Free Trees
• On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems
• A PTAS for ℓ_p-Low Rank Approximation
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• Segmentation problems
• Parameterized Algorithms

This page was built for publication: Parameterized complexity of categorical clustering with size constraints