Colloquium Schedule         Guidelines         Directions        

Thursday, April 24, 2014

Efficient Sequential and Multicore Weighted Matching Algorithms

Fredrik Manne (University of Bergen, Norway)

Abstract: The weighed matching problem asks for a subset of edges of a weighted graph such that no two edges are incident on the same vertex and such that the sum of the weight of the selected edges is as high as possible.This problem pops up in a number of scientific applications including sparse linear algebra. Although there exists polynomial time exact algorithms for this problem these are often too time consuming to be used on large problems. In this talk we first review the status of efficient approximation algorithms for weighted matching. We then present new sequential as well as multicore algorithms for this problem. We first give a one-phase sequential algorithm that is shown to be faster than the current fastest 0.5-approximation algorithms on sparse graphs. This is then extended to a two-phase algorithm that is both faster and gives better matchings than the current best linear time heuristics for this problem. Finally, we show that both of our algorithms are easily parallelizable on multicore computers. A number of experiments on different architectures verifies our claims and shows that the algorithms scale better than previous efforts at designing shared memory matching algorithms.

<<< previous talk
next talk >>>

Location :  Room 611 of the Hans Freudenthal building, formerly known as the Wiskunde/Maths building, (campus De Uithof) Budapestlaan 6, Utrecht.
Date and time : Thursday, April 24, 2014 15:30-16:30. The lecture is preceded by coffee, tea, and cookies from 15.00 to 15.30 hour in the same room.