A polynomial time algorithm for solving the fermat-weber location problem with mixed norms

Abstract

This paper discusses the Fermat-Weber location problem, manages to apply the ellipsoid method to this problem and proves the ellipsoid method can be terminated at an approximately optimal location in polynomial time, verifies the ellipsoid method is robust for the lower dimensional location problem

Keywords:

• Fermat-Weber Location
• Ellipsoid Method
• Subgradient
• Computational Complexity
• Mixed Norms

^*Sponsored by Natural Science Foundation of China

^*Sponsored by Natural Science Foundation of China

Notes

^*Sponsored by Natural Science Foundation of China