Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 17, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Stefano Tessaro
The integer programming problem is known to be NP-hard. However, if the dimension is considered to be constant, a well known algorithm by H.W. Lenstra requires O(m φ + φ2) arithmetic operations on rational numbers of size O(φ), where φ is the facet complexity of the integer program, and m the number of constraints.
In this talk, a new algorithm by Friedrich Eisenbrand for the special case where additionally the number of constraints is also constant is presented. This algorithm performs O(s) arithmetic operations on rational number with size bounded by O(s), where s is the size of the integer program. Moreover, even in the case where the number of constraints m is not a constant, this new algorithm can be used to obtain a Las Vegas algorithm for integer programming in fixed dimension which requires an expected number of O(m + φ log m) arithmetic operations on rational number of size O(φ), outperforming Lenstra's algorithm in expectation.
Automatic MiSe System Software Version 1.4803M | admin login