Abstract
In this paper we show how to express ordered median problems as a difference between two convex functions (DC). Such an expression can be exploited in solving ordered median problems by using the special methodology available for DC optimization. The approach is demonstrated for solving ordered one median problems in the plane. Computational experiments demonstrated the effectiveness of the approach.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Drezner Z.: A general global optimization approach for solving location problems in the plane. J. Global Optim. 37, 305–319 (2007)
Drezner, Z., Hamacher, H.W. (eds): Facility Location: Applications and Theory. Springer-Verlag, Berlin (2002)
Drezner, Z., Nickel, S.: Solving the Ordered One-Median Problem in the plane. Eur. J. Oper. Res. (2008) (to appear). doi:10.1016/j.ejor.2008.02.033
Drezner Z., Suzuki A.: The big triangle small triangle method for the solution of non-convex facility location problems. Oper. Res. 52, 128–135 (2004)
Drezner, T., Drezner, Z., Guyse, J.: The lorenz curve in location analysis. Technical Report (2007)
Horst R., Thoai Ng.V.: DC programming: overview. J. Optim. Theory Appl. 103, 1–43 (1999)
Horst R., Phong T.Q., Thoai Ng.V., de Vries J.: On solving a d.c. programming problem by a sequence of linear programs. J. Global Optim. 1, 183–203 (1991)
Kalcsics J., Nickel S., Puerto J., Tamir A.: Algorithmic results for ordered median problems defined on networks and the plane. Oper. Res. Lett. 30, 149–158 (2002)
Nickel S., Puerto J.: Facility Location—A Unified Approach. Springer-Verlag, Berlin (2005)
Ohya T., Iri M., Murota K.: Improvements of the incremental method of the voronoi diagram with computational comparison of various algorithms. J. Oper. Res. Soc. Jpn. 27, 306–337 (1984)
Plastria F.: Continuous location problems: research, results and questions. In: Drezner, Z. (eds) Facility Location: A Survey of Applications and Methods, pp. 85–127. Springer-Verlag, New York (1995)
Rodríguez-Chía A.M., Nickel S., Puerto J., Fernández F.R.: A flexible approach to location problems. Math. Methods Oper. Res. 51(1), 69–89 (2000)
Sugihara K., Iri M.: A robust topology-oriented incremental algorithm for voronoi diagram. Int. J. Comput. Geometry Appl. 4, 179–228 (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Drezner, Z., Nickel, S. Constructing a DC decomposition for ordered median problems. J Glob Optim 45, 187–201 (2009). https://doi.org/10.1007/s10898-008-9326-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9326-6