On an open problem in spherical facility location |
| |
Authors: | Guoliang Xue |
| |
Affiliation: | (1) Department of Computer Science and Electrical Engineering, The University of Vermont, 05405 Burlington, VT, USA |
| |
Abstract: | In this paper we partially resolve an open problem in spherical facility location. The spherical facility location problem is a generalization of the planar Euclidean facility location problem. This problem was first studied by Katz and Cooper and by Drezner and Wesolowsky where a Weszfeld-like algorithm was proposed. This algorithm is very simple and does not require a line search. However, its convergence has been an open problem for more than ten years. In this paper, we prove that the sequence generated by the algorithm converges to the unique optimal solution under the condition that the oscillation of the sequence converges to zero. We conjecture that the algorithm is a descent algorithm and prove that the sequence generated by the algorithm converges to the optimal solution under this conjecture. |
| |
Keywords: | Spherical facility location Euclidean facility location closed form iteration formula open problem convergence theorem |
本文献已被 SpringerLink 等数据库收录! |