首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 11 毫秒
1.
Tijs et al. [23] introduce the family of obligation rules for minimum cost spanning tree problems. We give a generalization of such family. We prove that our family coincides with the set of rules satisfying an additivity property and a cost monotonicity property. We also provide two new characterizations for the family of obligation rules using the previous properties. In the first one, we add a property of separability; and in the second one, we add core selection.  相似文献   

2.
We introduce optimistic weighted Shapley rules in minimum cost spanning tree problems. We define them as the weighted Shapley values of the optimistic game v+ introduced in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., forthcoming. The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Available from: <http://webs.uvigo.es/gbergant/papers/cstShapley.pdf>]. We prove that they are obligation rules [Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121–134].  相似文献   

3.
In the context of minimum cost spanning tree problems, we present a bargaining mechanism for connecting all agents to the source and dividing the cost among them. The basic idea is very simple: we ask each agent the part of the cost he is willing to pay for an arc to be constructed. We prove that there exists a unique payoff allocation associated with the subgame perfect Nash equilibria of this bargaining mechanism. Moreover, this payoff allocation coincides with the rule defined in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., 2007a. A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137, 326–352].  相似文献   

4.
Boruvka’s algorithm, which computes a minimum cost spanning tree, is used to define a rule to share the cost among the nodes (agents). We show that this rule coincides with the folk solution, a very well-known rule of this literature.  相似文献   

5.
In this paper we provide an axiomatic characterization of the folk rule for minimum cost spanning tree problems with multiple sources. The properties we need are: cone-wise additivity, cost monotonicity, symmetry, isolated agents, and equal treatment of source costs.  相似文献   

6.
本在Glover—Klingman算法及最小费用支撑树对策的基础上,讨论了最小费用k度限制树对策问题.利用威胁、旁支付理论制订了两种规则,并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解,从而证明了在这两种规则下其核心非空.  相似文献   

7.
This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.  相似文献   

8.
In this paper we consider the minimum cost spanning tree model. We assume that a central planner aims at implementing a minimum cost spanning tree not knowing the true link costs. The central planner sets up a game where agents announce link costs, a tree is chosen and costs are allocated according to the rules of the game. We characterize ways of allocating costs such that true announcements constitute Nash equilibria both in case of full and incomplete information. In particular, we find that the Shapley rule based on the irreducible cost matrix is consistent with truthful announcements while a series of other well-known rules (such as the Bird-rule, Serial Equal Split, and the Proportional rule) are not.  相似文献   

9.
10.
We associate an optimistic TU game with each minimum cost spanning tree problem. We define the worth of a coalition S as the cost of connecting agents in S to the source assuming that agents in N\S are already connected to the source, and agents in S can connect through agents in N\S. We study the Shapley value of this new game. We thank Hervé Moulin, William Thomson, and two referees for helpful comments. Financial support from the Ministerio de Ciencia y Tecnologia and FEDER through grant SEJ2005-07637-c02-01 is gratefully acknowledged.  相似文献   

11.
The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs with up 240 nodes.  相似文献   

12.
This paper deals with a minimum spanning tree problem where each edge cost includes uncertainty and importance measure. In risk management to avoid adverse impacts derived from uncertainty, a d-confidence interval for the total cost derived from robustness is introduced. Then, by maximizing the considerable region as well as minimizing the cost-importance ratio, a biobjective minimum spanning tree problem is proposed. Furthermore, in order to satisfy the objects of the decision maker and to solve the proposed model in mathematical programming, fuzzy goals for the objects are introduced as satisfaction functions, and an exact solution algorithm is developed using interactive decision making and deterministic equivalent transformations. Numerical examples are provided to compare our proposed model with some previous models.  相似文献   

13.
It is a known result that for a minimum cost spanning tree (mcst) game a Core allocation can be deduced directly from a mcst in the underlying network. To determine this Core allocation one only needs to determine a mcst in the network and it is not necessary to calculate the coalition values of the corresponding mcst game. In this paper we will deduce other Core allocations directly from the network, without determining the corresponding mcst game itself: we use an idea of Bird (cf. [4]) to present two procedures that determine a part of the Core (called the Irreducible Core) from the network.  相似文献   

14.
We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].  相似文献   

15.
Spanning tree problems defined in a preference-based environment are addressed. In this approach, optimality conditions for the minimum-weight spanning tree problem (MST) are generalized for use with other, more general preference orders. The main goal of this paper is to determine which properties of the preference relations are sufficient to assure that the set of ‘most-preferred’ trees is the set of spanning trees verifying the optimality conditions. Finally, algorithms for the construction of the set of spanning trees fulfilling the optimality conditions are designed, improving the methods in previous papers.  相似文献   

16.
17.
This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once.  相似文献   

18.
In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).  相似文献   

19.
We associate to each cost spanning tree problem a non-cooperative game, which is inspired by a real-life problem. We study the Nash equilibria and subgame perfect Nash equilibria of this game. We prove that these equilibria are closely related with situations where agents connect sequentially to the source.Finicial support from the Ministerio de Ciencia y Tecnologia and FEDER, and Xunta de Galicia through grants BEC2002-04102-C02-01 and PGIDIT03PXIC30002PN is gratefully acknowledged.  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号