Date:  16:3017:10, Wednesday, March 25, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Computing Frobenius Numbers Using Test Sets

Speaker:  Bjarke Hammersholt Roune 
Biography: 
Bjarke Hammersholt Roune is a graduate student in computer science and mathematITCS at Daimi at the University of Aarhus. His advisor is Peter Bro Miltersen and Niels Lauritzen. His research so far has focused on the Frobenius problem, computations on monomial ideals and maximal lattice free bodies.

Abstract: 
Suppose you have an infinite supply of coins that are worth respectively 6, 9, and 20 yuan. Then it is possible to hand out e.g. 12 yuan, while it is impossible to hand out 11 yuan. In fact 43 is the largest number that cannot be handed out in this case. In general, let a_1, ..., a_N be N relatively prime positive integers, and consider the largest integer that cannot be written as a positive integral combination of these numbers. This number is known as the Frobenius number, and in this talk we present an exponential but practical algorithm that can compute Frobenius numbers even when the input numbers a_i have a thousand digits. Thus the algorithm can solve some Frobenius problems of a size that has not been solved before. It is in effect an enhancement of the algorithm by Einstein, Lichtblau, Strzebonksi and Wagon.
