Pith. sign in

REVIEW

Lossy Kernelization of Same-Size Clustering

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2107.07383 v1 pith:2LOWNZEC submitted 2021-07-15 cs.DS

Sayan Bandyapadhyay , Fedor V. Fomin , Petr A. Golovach , Nidhi Purohit , Kirill Simonov This is my paper · ORCID
classification cs.DS
keywords clusteringproblemkernellossyparameterizedpolynomialresultadditional
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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 existences of an (exact) kernel of polynomial size and a PTAS.

Discussion (0). Continue with ORCID to comment.

Pith tools