Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 11, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Jan Remy
In this talk an online variant of the minimum spanning tree problem in random weighted graphs will be presented. We assume that the input graph is complete and the edge weights have uniform distribution over [0,1]. An algorithm receives the edges one by one in random order and has to decide immediately whether to include the current edge into the spanning tree or to reject it. As a performance measure we consider the expected competitive ratio E[r], where r=ALG/OPT. As our main result, we propose an online algorithm and show that its expected competitive ratio is O(1).
Automatic MiSe System Software Version 1.4803M | admin login