A service points location problem with min-max distance optimality criterion. (English) Zbl 0802.90062

The problem considered generalizes the problem of absolute center of a graph. Let us suppose that \(m\) points \(Y_ 1,\dots,Y_ m\) are given, which have to be supplied from \(n\) points \(S_ 1,\dots,S_ n\). Each service point \(S_ j\) is to be placed on a given segment \(A_ j B_ j\). We obtain the following optimization problem: \[ f(x_ 1,\dots, x_ n)\equiv \max_{1\leq j\leq n} \max_{1\leq i\leq m} r_{ij}(x_ j)\to \min \] subject to \(h_ j\leq x_ j\leq H_ j\) for \(j= 1,\dots,n\). The algorithm for solving the problem looks for minima of certain piecewise- linear non-convex functions and requires \(O(mn\log m)\) time.


90B80 Discrete location and assignment
90C27 Combinatorial optimization
Full Text: EuDML