Cost allocation for steiner trees
Cost allocation for steiner trees
复制标题
斯坦纳树的成本分配
作者：
N. Megiddo
一组称为消费者的点和另一个称为中央供应商的点位于欧几里德平面上。在两点之间构建连接的成本与它们之间的距离成正比。将所有消费者连接到供应商所需的最低成本由最小斯坦纳树给出。给出了一个例子，其中每次将树的总成本分配给消费者时，都会存在一个消费者联盟，该联盟所收取的费用高于将其成员连接到中央供应商所需的成本。
A set of points, called consumers, and another point called central supplier, are located in a Euclidean plane. The cost of constructing a connection between two points is proportional to the distance between them. The minimum cost required for connecting all the consumers to the supplier is given by a minimal Steiner tree. An example is given in which for every allocation of the total cost of the tree to the consumers, a coalition of consumers exists, which is charged more than the cost required for connecting its members to the central supplier.