Cost additive rules in minimum cost spanning tree problems with multiple sources
- PDF / 303,080 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 166 Views
Cost additive rules in minimum cost spanning tree problems with multiple sources Gustavo Bergantiños1 · Leticia Lorenzo1 Accepted: 7 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we introduce a family of rules in minimum cost spanning tree problems with multiple sources called Kruskal sharing rules. This family is characterized by cone-wise additivity and independence of irrelevant trees. We also investigate some subsets of this family and provide axiomatic characterizations of them. The first subset is obtained by adding core selection. The second is obtained by adding core selection and equal treatment of source costs. Keywords Minimum cost spanning tree problems · Multiple sources · Kruskal sharing rules · Axiomatic characterizations
1 Introduction Consider a problem where a group of agents is interested in goods provided by several suppliers or sources. To be served, the agents must be connected directly or indirectly to the suppliers which means that they incur a cost. Agents also want to be connected to all sources. This may be motivated by safety issues. There could also be situations in which each source provides a different resource (water, electricity, Internet connection, etc.) and agents are interested in all of them. In our model we first have to find the least costly structure (a tree) that connects all the agents to the sources directly or indirectly, taking into account that agents want to be connected to every source. Kruskal (1956) and Prim (1957) propose algorithms for selecting the least costly tree in the classical model, where there is a unique source. Such algorithms can also serve their purpose in the case of multiple sources with the same good characteristics as the polynomial computation time. Some authors have studied related problems that are difficult from a computational point of view. For instance, Granot and Granot (1992) study the fixed cost spanning forest problem; Farley et al. (2000) study how to compute the spanning tree that minimizes the sum of the distances from each source to every other node, Gouveia and Martins (1999) the capacitated minimal spanning tree problem, and Gouveia et al. (2014) study hop constrained Steiner trees with multiple root nodes.
B 1
Leticia Lorenzo [email protected] Economics, Society and Territory, Universidade de Vigo, 36310 Vigo, Spain
123
Annals of Operations Research
Once such a tree is obtained, its associated cost has to be shared among the agents. The many papers that have studied this issue in classical minimum cost spanning tree problems include Bird (1976), Kar (2002), Dutta and Kar (2004), Bergantiños and Vidal-Puga (2007), Bogomolnaia and Moulin (2010), Trudeau (2012), and Bergantiños and Gómez-Rúa (2015). But there are few papers for the case of multiple sources. Rosenthal (1987) assumes that all sources provide the same service and agents want to be connected to at least one of them. He associates a cooperative game with this problem and studies the core. Kuipers
Data Loading...
