A Technical Report on PLS-Completeness of Single-Swap for Unweighted Metric Facility Location and $K$-Means

Abstract

Recently, [Bra17] showed that the single-swap heuristic for weighted metric uncapacitated facility location and $K$-Means is tightly PLS-complete. We build upon this work and present a stronger reduction, which proves tight PLS-completeness for the unweighted version of both problems.

arXiv commentarXiv admin note: text overlap with arXiv:1612.01752