A linear algorithm for integer programming in the plane
Eisenbrand, Friedrich; Laue, Sören
2005

Files

Résumé

We show that a 2-variable integer program, defined by m constraints involving coefficients with at most φ bits, can be solved with O(m+φ) arithmetic operations on rational numbers of size O(φ). © Springer-Verlag 2004.

Détails

Titre A linear algorithm for integer programming in the plane
Auteur(s) Eisenbrand, Friedrich ; Laue, Sören
Publié dans Mathematical Programming
Volume 102
Numéro 2
Pages 249-259
Date 2005
DOI https://doi.org/10.1007/s10107-004-0520-0
Laboratoires DISOPT
Le document apparaît dans Production scientifique et compétences > SB - Faculté des sciences de base > MATH - Institut de mathématiques > DISOPT - Chaire d'optimisation discrète
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail hors EPFL
Articles de journaux
Publié
Date de création de la notice 2008-05-13

PDF