The tollbooth problem aims at minimizing the time lost through congestion in road networks with rational and selfish participants by demanding an additional toll for the use of edges. In the talk, a variant of this problem is considered, the minimum tollbooth problem, which additionally minimizes the number of tolled edges. A novel probabilistic divide and conquer algorithm solving the problem is presented.
30.10. 15:00 - A Probabilistic Divide and Conquer Algorithm for the Minimum Tollbooth Problem
Uwe Baier Universität Ulm
Vortrag "A Probabilistic Divide and Conquer Algorithm for the Minimum Tollbooth Problem" gehalten von Julian Nickerl.