Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Mittagsseminar Talk Information

Date and Time: Tuesday, November 11, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Lenny Fukshansky (Claremont McKenna College)

On the Frobenius problem and its generalization

Let N > 1 be an integer, and let 1 < a_1 < ... < a_N be relatively prime integers. Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be represented as a linear combination of a_1,...,a_N with non-negative integer coefficients. More generally, the s-Frobenius number is defined to be the largest positive integer that has precisely s distinct representations like this, so that the classical Frobenius number can be thought of as the 0-Frobenius number. The condition that a_1,...,a_N are relatively prime implies that s-Frobenius numbers exist for every non-negative integer s. The general problem of determining the Frobenius number, given N and a_1,...,a_N, dates back to the 19-th century lectures of G. Frobenius and work of J. Sylvester, and has been studied extensively by many prominent mathematicians of the 20-th century, including P. Erdos. While this problem is now known to be NP-hard, there has been a number of successful efforts by various authors producing bounds and asymptotic estimates on the Frobenius number and its generalization. I will discuss some of these results, which are obtained by an application of techniques from Discrete Geometry.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login