# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 30.10.2008 at 12:20 in S6, there is the following noon lecture:

# 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

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010