TY - CHAP
AB - 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.
AU - Brauer, Sascha
ED - Fotakis, Dimitris
ED - Pagourtzis, Aris
ED - Paschos, Vangelis Th.
ID - 2381
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
VL - 10236
ER -