## 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.

### MSC:

 90B80 Discrete location and assignment 90C27 Combinatorial optimization

### Keywords:

location theory; absolute center of a graph
Full Text: