Sponsor
The research leading to these results have been supported by the Research Council of Norway via the project BWCA (grant no. 314528), European Research Council (ERC) via grant LOPPRE, reference 819416, and DFG Research Group ADYN via grant DFG 411362735. Open access funding provided by University of Bergen (incl Haukeland University Hospital)
Published In
Theory of Computing Systems
Document Type
Article
Publication Date
7-2023
Subjects
Parameterized approximation -- Kernelization
Abstract
In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existence of an (exact) kernel of polynomial size and a PTAS.
Rights
Copyright (c) 2023 The Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
Locate the Document
DOI
10.1007/s00224-023-10129-9
Persistent Identifier
https://archives.pdx.edu/ds/psu/40648
Citation Details
Bandyapadhyay, S., Fomin, F. V., Golovach, P. A., Purohit, N., & Simonov, K. (2023). Lossy kernelization of same-size clustering. Theory of Computing Systems, 1-40.