One-Center Location With Block and Euclidean Distance.

Area of Science:

• Operations Research
• Computational Geometry
• Optimization

Background:

• The one-center location problem seeks a point minimizing the maximum distance to a set of sites.
• Linear programming and the simplex algorithm are standard tools for solving such problems.
• Dual algorithms offer alternative approaches to optimization problems.

Purpose of the Study:

• To geometrically analyze the dual simplex algorithm applied to the one-center location problem in a 2D plane using block distance.
• To develop a geometric rule for updating the dual basis within the simplex algorithm.
• To adapt this geometric analysis for the Euclidean distance one-center problem.

Main Methods:

• Geometrical analysis of the dual simplex algorithm.
• Formulation of the one-center location problem using linear programming.
• Derivation of a geometric rule for dual basis updates.
• Application to the Euclidean distance variant.

Main Results:

• A geometric rule equivalent to the minimum ratio rule for dual basis updates was identified.
• The geometric analysis provides an alternative updating procedure for the dual algorithm.
• This approach is applicable to both block and Euclidean distances in the one-center problem.

Conclusions:

• The geometric perspective offers valuable insights into the dual simplex algorithm for location problems.
• The derived geometric rule provides an alternative and potentially more intuitive method for dual basis updates.
• This work contributes to the understanding and efficiency of solving geometric optimization problems.