Parameterized complexity of categorical clustering with size constraints

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

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

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

Cites Work

• Closest Substring Problems with Small Distances
• Color-coding
• Parameterized Algorithms
• The number of trees
• Achieving anonymity via clustering
• Matroid and knapsack center problems
• Segmentation problems
• A constant-factor approximation algorithm for the \(k\)-median problem
• The complexity of the single individual SNP haplotyping problem
• Constant Time Generation of Free Trees
• Approximating \(k\)-median with non-uniform capacities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kernelization
• Parameterized low-rank binary matrix approximation
• Parameterized \(k\)-clustering: tractability island
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Polynomial-time approximation schemes for geometric min-sum median clustering
• Clustering with balancing constraints
• Title not available (Why is that?)
• 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

Cited In (2)

• On the Complexity of Clustering with Relaxed Size Constraints
• Lossy kernelization of same-size clustering

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

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