Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees

Mordechai Jaeger and Jeff Goldberg
Additional contact information
Mordechai Jaeger: Department of Systems and Industrial Engineering, University of Arizona, Tucson, Arizona 85721
Jeff Goldberg: Department of Systems and Industrial Engineering, University of Arizona, Tucson, Arizona 85721

Transportation Science, 1994, vol. 28, issue 2, 167-175

Abstract: The uncapacitated p -center problem has been shown to be NP-Hard for the case of a general network, yet polynomial algorithms exist for the case of a tree network. We extend the results for trees to include the case where each center can serve a limited number of customers and show that the capacitated p -center problem on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. We show that the addition of center capacities to either the vertex center problem or the absolute center problem requires a multiplicative factor of O ( n ) more work, relative to that required for the uncapacitated problems, to solve the related covering problems ( n is the number of vertices in the tree).

Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.28.2.167 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:28:y:1994:i:2:p:167-175

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().