Best location of service centers in a treelike network under budget constraints
✍ Scribed by James McHugh; Yehoshua Perl
- Publisher
- Elsevier Science
- Year
- 1990
- Tongue
- English
- Weight
- 1016 KB
- Volume
- 86
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the problem of locating service centers in a treelike network in order to maximize the serviced population under budget constraints. We show that the problem is NP-hard. In the case where the costs of establishing the service centers are equal for all n cities we obtain the maximum weight k-domination problem.
An O(nk') dynamic programming procedure is given. Then an 0(&a) pseudo-polynomial dynamic programming procedure is presented for the original problem, where B is the budget constraint. Finally a variation of the new left-right dynamic programming technique is applied to obtain a more efficient pseudo-polynomial procedure.