Complexity of local search for the p-median problem
We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0-1 local saddle points, and classical Karush-Kuhn-Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.
Year of publication: |
2008
|
---|---|
Authors: | Alekseeva, Ekaterina ; Kochetov, Yuri ; Plyasunov, Alexander |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 191.2008, 3, p. 736-752
|
Publisher: |
Elsevier |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Complexity of local search for the p-median problem
Alekseeva, Ekaterina, (2008)
-
Competitive location m cognitive radio networks
Iellamo, Stefano, (2015)
-
A matheuristic for the discrete bilevel problem with multiple objectives at the lower level
Alekseeva, Ekaterina, (2017)
- More ...