The Broadcast Assignment Problem

摘要

For pricing considerations, Herzog et al. proposed Cost Allocation schemes for broadcast transmissions via a given broadcast tree that define the Assignment for a participant. In a particular scheme, the Assignment for a participant is the sum of the cost of each link on the unique path of the tree from the transmitter of the broadcast to the participant. The cost of a link is the inverse of the number of participants in the subtree attached by this link to the tree. They proved that this Cost Allocation scheme has interesting properties (like fairness). We propose to investigate the problem of constructing a minimum assignment spanning tree (i.e. the tree minimizing the maximal assignment). We first show that considering shortest paths (from the transmitter of the broadcast) spanning (broadcast) trees can lead to very high cost assignments in the worst case (value depending on the size of the graph). Then, we show that the problem is NP-complele. Finally, we concentrate on the study of an important family of graphs, namely the square mesh and torus. For any size of such graphs and any root we construct a spanning tree with constant assignment.