Parameterized complexity of categorical clustering with size constraints

DOI10.1016/j.jcss.2023.03.006OpenAlexW3155470024MaRDI QIDQ6098152

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

Publication date: 12 June 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2023.03.006

zbMATH Keywords

kernelization\(k\)-mediancategorical clusteringfixed-parameterized algorithm

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid and knapsack center problems
• Fundamentals of parameterized complexity
• 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