Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, piano terzo
Aula Seminari

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)