dc.contributor.author | Bandyapadhyay, Sayan | |
dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Purohit, Nidhi | |
dc.contributor.author | Simonov, Kirill | |
dc.date.accessioned | 2023-09-15T11:36:38Z | |
dc.date.available | 2023-09-15T11:36:38Z | |
dc.date.created | 2023-09-05T15:01:21Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 1432-4350 | |
dc.identifier.uri | https://hdl.handle.net/11250/3089739 | |
dc.description.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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Lossy Kernelization of Same-Size Clustering | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2023 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1007/s00224-023-10129-9 | |
dc.identifier.cristin | 2172649 | |
dc.source.journal | Theory of Computing Systems | en_US |
dc.source.pagenumber | 785-824 | en_US |
dc.identifier.citation | Theory of Computing Systems. 2023, 67 (4), 785-824. | en_US |
dc.source.volume | 67 | en_US |
dc.source.issue | 4 | en_US |