Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
S. Brauer, in: D. Fotakis, A. Pagourtzis, V.T. Paschos (Eds.), Lecture Notes in Computer Science, Springer International Publishing, Cham, 2017, pp. 116–127.
Download
No fulltext has been uploaded.
Book Chapter
| Published
| English
Author
Book Editor
Fotakis, Dimitris;
Pagourtzis, Aris;
Paschos, Vangelis Th.
Department
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.
Publishing Year
Book Title
Lecture Notes in Computer Science
Volume
10236
Page
116-127
Conference
10th International Conference on Algorithms and Complexity
Conference Location
Athens, Greece
Conference Date
2017-05-24 – 2017-05-26
ISBN
LibreCat-ID
Cite this
Brauer S. Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems. In: Fotakis D, Pagourtzis A, Paschos VT, eds. Lecture Notes in Computer Science. Vol 10236. Cham: Springer International Publishing; 2017:116-127. doi:10.1007/978-3-319-57586-5_11
Brauer, S. (2017). Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems. In D. Fotakis, A. Pagourtzis, & V. T. Paschos (Eds.), Lecture Notes in Computer Science (Vol. 10236, pp. 116–127). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-57586-5_11
@inbook{Brauer_2017, place={Cham}, title={Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems}, volume={10236}, DOI={10.1007/978-3-319-57586-5_11}, 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} }
Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” In Lecture Notes in Computer Science, edited by Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, 10236:116–27. Cham: Springer International Publishing, 2017. https://doi.org/10.1007/978-3-319-57586-5_11.
S. Brauer, “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems,” in Lecture Notes in Computer Science, vol. 10236, D. Fotakis, A. Pagourtzis, and V. T. Paschos, Eds. Cham: Springer International Publishing, 2017, pp. 116–127.
Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” Lecture Notes in Computer Science, edited by Dimitris Fotakis et al., vol. 10236, Springer International Publishing, 2017, pp. 116–27, doi:10.1007/978-3-319-57586-5_11.
Google Scholar
ISBN Search