---
_id: '2381'
abstract:
- lang: eng
  text: 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:
- first_name: Sascha
  full_name: Brauer, Sascha
  id: '13291'
  last_name: Brauer
citation:
  ama: 'Brauer S. Complexity of Single-Swap Heuristics for Metric Facility Location
    and Related Problems. In: Fotakis D, Pagourtzis A, Paschos VT, eds. <i>Lecture
    Notes in Computer Science</i>. Vol 10236. Cham: Springer International Publishing;
    2017:116-127. doi:<a href="https://doi.org/10.1007/978-3-319-57586-5_11">10.1007/978-3-319-57586-5_11</a>'
  apa: 'Brauer, S. (2017). Complexity of Single-Swap Heuristics for Metric Facility
    Location and Related Problems. In D. Fotakis, A. Pagourtzis, &#38; V. T. Paschos
    (Eds.), <i>Lecture Notes in Computer Science</i> (Vol. 10236, pp. 116–127). Cham:
    Springer International Publishing. <a href="https://doi.org/10.1007/978-3-319-57586-5_11">https://doi.org/10.1007/978-3-319-57586-5_11</a>'
  bibtex: '@inbook{Brauer_2017, place={Cham}, title={Complexity of Single-Swap Heuristics
    for Metric Facility Location and Related Problems}, volume={10236}, DOI={<a href="https://doi.org/10.1007/978-3-319-57586-5_11">10.1007/978-3-319-57586-5_11</a>},
    booktitle={Lecture Notes in Computer Science}, publisher={Springer International
    Publishing}, author={Brauer, Sascha}, editor={Fotakis, Dimitris and Pagourtzis,
    Aris and Paschos, Vangelis Th.Editors}, year={2017}, pages={116–127} }'
  chicago: 'Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility
    Location and Related Problems.” In <i>Lecture Notes in Computer Science</i>, edited
    by Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, 10236:116–27.
    Cham: Springer International Publishing, 2017. <a href="https://doi.org/10.1007/978-3-319-57586-5_11">https://doi.org/10.1007/978-3-319-57586-5_11</a>.'
  ieee: 'S. Brauer, “Complexity of Single-Swap Heuristics for Metric Facility Location
    and Related Problems,” in <i>Lecture Notes in Computer Science</i>, vol. 10236,
    D. Fotakis, A. Pagourtzis, and V. T. Paschos, Eds. Cham: Springer International
    Publishing, 2017, pp. 116–127.'
  mla: Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location
    and Related Problems.” <i>Lecture Notes in Computer Science</i>, edited by Dimitris
    Fotakis et al., vol. 10236, Springer International Publishing, 2017, pp. 116–27,
    doi:<a href="https://doi.org/10.1007/978-3-319-57586-5_11">10.1007/978-3-319-57586-5_11</a>.
  short: 'S. Brauer, in: D. Fotakis, A. Pagourtzis, V.T. Paschos (Eds.), Lecture Notes
    in Computer Science, Springer International Publishing, Cham, 2017, pp. 116–127.'
conference:
  end_date: 2017-05-26
  location: Athens, Greece
  name: 10th International Conference on Algorithms and Complexity
  start_date: 2017-05-24
date_created: 2018-04-17T12:20:53Z
date_updated: 2022-01-06T06:56:00Z
department:
- _id: '64'
doi: 10.1007/978-3-319-57586-5_11
editor:
- first_name: Dimitris
  full_name: Fotakis, Dimitris
  last_name: Fotakis
- first_name: Aris
  full_name: Pagourtzis, Aris
  last_name: Pagourtzis
- first_name: Vangelis Th.
  full_name: Paschos, Vangelis Th.
  last_name: Paschos
intvolume: '     10236'
language:
- iso: eng
page: 116-127
place: Cham
publication: Lecture Notes in Computer Science
publication_identifier:
  isbn:
  - '9783319575858'
  - '9783319575865'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer International Publishing
status: public
title: Complexity of Single-Swap Heuristics for Metric Facility Location and Related
  Problems
type: book_chapter
user_id: '13291'
volume: 10236
year: '2017'
...