On the complexity of locating linear facilities in the plane |
| |
Authors: | Nimrod Megiddo Arie Tamir |
| |
Affiliation: | Statistics Department, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | We consider the computational complexity of linear facility location problems in the plane, i.e., given n demand points, one wishes to find r lines so as to minimize a certain objective-function reflecting the need of the points to be close to the lines. It is shown that it is NP-hard to find r lines so as to minimize any isotone function of the distances between given points and their respective nearest lines. The proofs establish NP-hardness in the strong sense. The results also apply to the situation where the demand is represented by r lines and the facilities by n single points. |
| |
Keywords: | p-line center p-line median planar location NP-complete strongly NP-complete |
本文献已被 ScienceDirect 等数据库收录! |