Abstract:

Two approximate optimality conditions of the weighted Euclidean onecenter (WEOC) problem were defined. Based on the idea of sequential minimal optimization (SMO) method, an SMOtype algorithm for the WEOC problem was proposed. By means of this algorithm, a (1+ε)approximate solution of the WEOC problem was computed, which satisfys the second approximate optimality condition. At each iteration, it updates only two components of the dual variable. The numerical results show the proposed SMOtype algorithm is simple to implement, can effectively solve largescale problem with a high degree of accuracy.

Key words: weighted Euclidean onecenter, sequential minimal optimization, optimality condition, approximation algorithm