The Econoic Addition of Functionality to a Network

摘要

In the operation of communication and computer networks. it may become desirable or necessary to add a new function to the netcertain existing user locations. This will involve deciding which user locations will have devices placed at therm as well as deciding an assignment of users to device locations. The objective when adding the new function is to choose these lcoations and assignments such that the combined cost of placing the devices and routing users to their assigned device locations is minimized. This problem, which we calle the device placement problem, is closely related to the simple plant location problem and the p-median problem. Like these problems, the device placement problem is NP-hard, and thus it is highly unlikely that efficient methods for solving this preoblem to optimality exist.