26 April 2013, Computational Social Choice Seminar, Femke Bekius

Abstract

Given a source, a set of agents, and links with corresponding costs between agents, the source and agents themselves, the minimum cost spanning tree problem can be formulated by asking the following two questions: First, how can we find the cheapest set of links that will connect each agent to the source, either directly or indirectly, i.e., how can we find a tree which minimizes the total cost? Second, given this tree, how can one allocate the cost among the different agents in a fair way? In the literature several algorithms, charge rules, and properties satisfying these charge rules are defined. This talk will give an overview of the most important algorithms, charge rules, and corresponding properties.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).