On 30.10.2008 at 12:20 in S6, there is the following noon lecture:
Frobenius problem: Applications
Universite de Paris VI
Note the unusual place!
This is a third part of the special series of lectures about Frobenius problem. (The first two are on Wednesday, on 9:00, and on 15:40, both in S6.)
Lecture I (Wednesday 29 October) Frobenius problem: Algorithms and complexity
F.G. Frobenius raised the following problem (called, Frobenius diophantine Problem [FP]): given relatively prime positive integers a_1,a_2,...,a_n, find the largest natural number, called the Frobenius number and denoted by g(a_1,a_2,...,a_n), that is not representable as a nonnegative integer combination of a_1,a_2,...,a_n. This lecture will be devoted to the computational aspects of FP. After showing that FP is NP-hard (under Turing reductions), we shall present a variety of algorithms to compute g(a_1,a_2,...,a_n) for general n. We will also discuss polynomial time methods that solve FP for some particular cases, for instance, when
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010