@inbook{2381,
  abstract     = {{Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.}},
  author       = {{Brauer, Sascha}},
  booktitle    = {{Lecture Notes in Computer Science}},
  editor       = {{Fotakis, Dimitris and Pagourtzis, Aris and Paschos, Vangelis Th.}},
  isbn         = {{9783319575858}},
  issn         = {{0302-9743}},
  location     = {{Athens, Greece}},
  pages        = {{116--127}},
  publisher    = {{Springer International Publishing}},
  title        = {{{Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems}}},
  doi          = {{10.1007/978-3-319-57586-5_11}},
  volume       = {{10236}},
  year         = {{2017}},
}