TY - JOUR

T1 - General models in min-max planar location

T2 - Checking optimality conditions

AU - Frenk, J. B.G.

AU - Gromicho, J.

AU - Zhang, S.

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1996/4

Y1 - 1996/4

N2 - This paper studies the problem of deciding whether the present iteration point of some algorithm applied to a planar single-facility min-max location problem, with distances measured by either an lp-norm or a polyhedral gauge, is optimal or not. It turns out that this problem is equivalent to the decision problem of whether 0 belongs to the convex hull of either a finite number of points in the plane or a finite number of different lq-circles ⊆ ℝ2. Although both membership problems are theoretically solvable in polynomial time, the last problem is more difficult to solve in practice than the first one. Moreover, the second problem is solvable only in the weak sense, i.e., up to a predetermined accuracy. Unfortunately, these polynomial-time algorithms are not practical. Although this is a negative result, it is possible to construct an efficient and extremely simple linear-time algorithm to solve the first problem. Moreover, this paper describes an implementable procedure to reduce the second decision problem to the first with any desired precision. Finally, in the last section, some computational results for these algorithms are reported.

AB - This paper studies the problem of deciding whether the present iteration point of some algorithm applied to a planar single-facility min-max location problem, with distances measured by either an lp-norm or a polyhedral gauge, is optimal or not. It turns out that this problem is equivalent to the decision problem of whether 0 belongs to the convex hull of either a finite number of points in the plane or a finite number of different lq-circles ⊆ ℝ2. Although both membership problems are theoretically solvable in polynomial time, the last problem is more difficult to solve in practice than the first one. Moreover, the second problem is solvable only in the weak sense, i.e., up to a predetermined accuracy. Unfortunately, these polynomial-time algorithms are not practical. Although this is a negative result, it is possible to construct an efficient and extremely simple linear-time algorithm to solve the first problem. Moreover, this paper describes an implementable procedure to reduce the second decision problem to the first with any desired precision. Finally, in the last section, some computational results for these algorithms are reported.

KW - Computational geometry

KW - Continuous location theory

KW - Convex hull

KW - Newton-Raphson method

KW - Optimality conditions

UR - http://www.scopus.com/inward/record.url?scp=0030539474&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030539474&partnerID=8YFLogxK

U2 - 10.1007/BF02192641

DO - 10.1007/BF02192641

M3 - Article

AN - SCOPUS:0030539474

SN - 0022-3239

VL - 89

SP - 65

EP - 87

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 1

ER -