Universiteit van Amsterdam

Archives

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Please note that this newsitem has been archived, and may contain outdated information or links.