TY - JOUR
T1 - Best location of service centers in a treelike network under budget constraints
AU - McHugh, James
AU - Perl, Yehoshua
N1 - Funding Information:
in part by the State of New Jersey SBR Grants.
PY - 1990/12/14
Y1 - 1990/12/14
N2 - 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(nk2) dynamic programming procedure is given. Then an O(nB2) 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.
AB - 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(nk2) dynamic programming procedure is given. Then an O(nB2) 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.
UR - http://www.scopus.com/inward/record.url?scp=38249017853&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249017853&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(90)90361-K
DO - 10.1016/0012-365X(90)90361-K
M3 - Article
AN - SCOPUS:38249017853
SN - 0012-365X
VL - 86
SP - 199
EP - 214
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -