[{"year":"2017","date_created":"2018-04-17T12:20:53Z","publisher":"Springer International Publishing","title":"Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems","publication":"Lecture Notes in Computer Science","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."}],"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783319575858","9783319575865"]},"citation":{"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.","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>.","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>","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.","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} }"},"page":"116-127","intvolume":"     10236","place":"Cham","author":[{"first_name":"Sascha","full_name":"Brauer, Sascha","id":"13291","last_name":"Brauer"}],"volume":10236,"date_updated":"2022-01-06T06:56:00Z","doi":"10.1007/978-3-319-57586-5_11","conference":{"location":"Athens, Greece","end_date":"2017-05-26","start_date":"2017-05-24","name":"10th International Conference on Algorithms and Complexity"},"type":"book_chapter","status":"public","editor":[{"last_name":"Fotakis","full_name":"Fotakis, Dimitris","first_name":"Dimitris"},{"first_name":"Aris","last_name":"Pagourtzis","full_name":"Pagourtzis, Aris"},{"full_name":"Paschos, Vangelis Th.","last_name":"Paschos","first_name":"Vangelis Th."}],"user_id":"13291","department":[{"_id":"64"}],"_id":"2381"}]