کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481260 | 1446162 | 2008 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Complexity of local search for the p-median problem Complexity of local search for the p-median problem](/preview/png/481260.png)
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.
Journal: European Journal of Operational Research - Volume 191, Issue 3, 16 December 2008, Pages 736–752