scientific article; zbMATH DE number 3843458
In this paper two discrete location problems are discussed. It is assumed that clients are located at the vertices of a tree network. Facilities have to be established on the tree in order to supply the clients. There is a budget constraint on the total setup cost associated with the facilities. Furthermore it is assumed that the transportation cost between client and facility is a continuous nondecreasing function of their distance. For ease of exposition a linear function has been chosen. The problems considered are to find locations of the facilities such that the budget constraint is statisfied and so as to minimize the maximum transportation cost. In the first problem it is assumed that facilities can be located anywhere on the tree and all setup costs are equal. In this case the budget constraint reduces to an upper bound, say p, on the number of facilities. It is shown how the concept of a chordal graph can be used to derive strong duality results for this so called p-center problem. In the second problem it is assumed that facilities can be located at a finite set of points, say the vertices, of the tree and that setup costs may differ. It is shown that this problem can be solved as a series of set covering problems on a (0,1)-matrix in standard greedy form for which a polynomial time algorithm is given.
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Best location of service centers in a treelike network under budget constraints
- Two classes of location problems on tree networks
- scientific article; zbMATH DE number 4202013 (Why is no real title available?)
- scientific article; zbMATH DE number 3950165 (Why is no real title available?)
- The Round-Trip p-Center and Covering Problem on a Tree
- Duality between distant point and median of a tree network space
- Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems
- scientific article; zbMATH DE number 58448 (Why is no real title available?)
- scientific article; zbMATH DE number 1022482 (Why is no real title available?)
- scientific article; zbMATH DE number 961964 (Why is no real title available?)
- Dually chordal graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313580)