Archives

Institute for Logic, Language and Computation


26 April 2013, Computational Social Choice Seminar, Femke Bekius

Speaker: Femke Bekius
Title: The Minimum Cost Spanning Tree Problem
Date: Friday 26 April 2013
Time: 16:00
Location: Room F1.15, Science Park 107, Amsterdam

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 ().


The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X