General models in min-max planar location: Checking optimality conditions

J. B.G. Frenk, J. Gromicho, S. Zhang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)65-87
Number of pages23
JournalJournal of Optimization Theory and Applications
Volume89
Issue number1
DOIs
StatePublished - Apr 1996

Keywords

  • Computational geometry
  • Continuous location theory
  • Convex hull
  • Newton-Raphson method
  • Optimality conditions

Fingerprint Dive into the research topics of 'General models in min-max planar location: Checking optimality conditions'. Together they form a unique fingerprint.

Cite this