Frobenius problem: Applications

Jorge Ramirez

Universite de Paris VI

Abstract

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