zbMATH — the first resource for mathematics

Balanced location on a graph. (English) Zbl 0874.90114
Summary: The problem of locating service facilities with respect to a given set of demands on a graph is considered. The objective function to be minimized is equal to the maximum difference in the distance from a demand point to its farthest and nearest facility (balancing function). It is assumed that any facility has at most $$m$$ possibilities for its location. For $$m=2$$, the computational complexity of the problem is $$O(np^2\log p)$$, where $$n$$ is the number of demand points and $$p$$ is the number of located facilities. For $$m>2$$, the problem is NP-hard. Similar results are presented for boolean and strongly boolean versions of the problem.

MSC:
 90B80 Discrete location and assignment 90C35 Programming involving graphs or networks 90C60 Abstract computational complexity for mathematical programming problems
Full Text:
References:
 [1] Gavalec, M. Computational Complexity of Consistent Choice Proceedings of the VI. Conference of EF TU. pp.70–74. Košice: Mathematical Section. [2] Halpern I., Accord and Conflict Among Several Objectives in Locational Decisions on Tree Networks (1983) [3] Handler G.Y., Location on Networks (1979) · Zbl 0533.90026 [4] Hansen P., An Algorithm for the Variance Point of a Network, RAIRO Rech. Oper 25 pp 119– (1991) · Zbl 0742.90048 [5] Hudec O., Zeitsch. Oper. Res 36 pp 439– (1992) [6] DOI: 10.1137/0405033 · Zbl 0825.68494 [7] DOI: 10.1287/mnsc.29.4.482 · Zbl 0513.90022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.