---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sascha
foaf_name: Brauer, Sascha
foaf_surname: Brauer
foaf_workInfoHomepage: http://www.librecat.org/personId=13291
bibo_doi: 10.1007/978-3-319-57586-5_11
bibo_volume: 10236
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783319575858
- http://id.crossref.org/issn/9783319575865
dct_language: eng
dct_publisher: Springer International Publishing@
dct_title: Complexity of Single-Swap Heuristics for Metric Facility Location and
Related Problems@
...