An important problem in distance geometry is of determining the position of an unknown point in a given convex set such that its longest distance to a set of finite number of points is shortest. In this paper we present an algorithm based on subgradient method and convex hull computation for solving this problem. A recent improvement of Quickhull algorithm for computing the convex hull of a finite set of planar points is applied to fasten up the computations in our numerical experiments.
Accepté le :
DOI : 10.1051/ro/2014058
Mots-clés : Location problem, distance geometry, convex hull, Quickhull algorithm, subgradient method
@article{RO_2015__49_3_589_0,
author = {Linh, Nguyen Kieu and Muu, Le Dung},
title = {A convex {Hull} algorithm for solving a location problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {589--600},
publisher = {EDP-Sciences},
volume = {49},
number = {3},
year = {2015},
doi = {10.1051/ro/2014058},
mrnumber = {3349136},
zbl = {1321.52001},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2014058/}
}
TY - JOUR AU - Linh, Nguyen Kieu AU - Muu, Le Dung TI - A convex Hull algorithm for solving a location problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 589 EP - 600 VL - 49 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014058/ DO - 10.1051/ro/2014058 LA - en ID - RO_2015__49_3_589_0 ER -
%0 Journal Article %A Linh, Nguyen Kieu %A Muu, Le Dung %T A convex Hull algorithm for solving a location problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 589-600 %V 49 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014058/ %R 10.1051/ro/2014058 %G en %F RO_2015__49_3_589_0
Linh, Nguyen Kieu; Muu, Le Dung. A convex Hull algorithm for solving a location problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 589-600. doi : 10.1051/ro/2014058. http://archive.numdam.org/articles/10.1051/ro/2014058/
and , A fast convex hull algorithm, Inform. Process. Lett. 7 (1978) 219–222. | DOI | MR | Zbl
, Method of orienting curves for determining the convex hull of a finite set of points in the plane. Optimization 59 (2010) 175–179. | DOI | MR | Zbl
, , and , On the average number of maxima in a set of vectors and application. J. Assoc. Comput. Machine 25 (1978) 536–543. | DOI | MR | Zbl
S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press (2004). | MR | Zbl
M.M. David, Computation geometry. Department of Computer Science (2002).
H.N. Dung and N.K. Linh, Quicker than Quickhull. Viet. J. Math. (2014) DOI:10.1007/s10013-014-0067-1. | MR
, , and , The minisum and minimax location problems revisited. Oper. Res. 33 (1985) 1251–1265. | DOI | MR | Zbl
and , A single facility minisum location problem under the A-distance. J. Oper. Res. Soc. Jpn 40 (1997) 10–20. | MR | Zbl
Y. Nesterov, Introductory lectures on convex optimization: A basic course. Kluwer Academic Publishers (2004). | MR | Zbl
J. O’Rourke, Computational geometry in C, 2nd edn. Cambridge University Press (1998). | MR | Zbl
, The generalized big square small square method for planar single facility location. Eur. J. Oper. Res. 62 (1992) 163–174. | DOI | Zbl
R.T. Rockafellar, Convex Analysis, Princeton University Press (1970). | MR | Zbl
A.P. Ruszczynski, Nonlinear Optimization, Princeton University Press (2006). | MR | Zbl
H. Tuy, A general d.c. approach to location problems. In State of the art in global optimization: Computational methods and applications, edited by C.A. Floudas and P.M. Pardalos. Kluwer (1996), 413–432. | MR | Zbl
, An iterative approach to quadratic optimization. J. Optim. Theor. Appl. 116 (2003) 659–678. | DOI | MR | Zbl
Cité par Sources :
