Campus Event Calendar
Event Entry
New for: D3
What and Who
Fast 2-variable integer programming
Fritz Eisenbrand
Max-Planck-Institut für Informatik - AG 2
AG2 Seminar
AG 1, AG 2, AG 3, AG 4
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 23 February 2001
13:15
45 Minutes
MPI
024
Saarbrücken
Abstract
We show that a 2-dimensional integer program, defined by $m$
constraints, can be solved with $\log(m)$ gcd-like computations.
If the number of constraints is fixed, our algorithm has
quasi-linear bit-complexity, which closes the
gap between the fastest gcd algorithms and 2-variable
integer programming with a fixed number of constraints.
(Joint work with Guenter Rote FU-Berlin)
Contact
Friedrich Eisenbrand
229
--email hidden
passcode not visible
logged in users only