Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Gallato, Martina (2019) Integer programming in the plane. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
759Kb

Abstract

In this work we study the problem of integer programming in fixed dimension, with a particular focus on the problem in dimension 2. Integer programming in dimension 2 is linked to elementary algorithmic number theory. In particular, the problem of computing the greatest common divisor of 2 integers is a 2-dimensional IP (that clearly can be solved by the Euclidean Algorithm). Many results in IP in dimension 2 have their foundation in the theory of lattices and continued fractions. IP in dimension 2 has been extensively studied and today many algorithms are known to solve an integer problem in dimension 2 in polynomial time. Specifically, in this work we study the currently fastest algorithm which solves an integer problem in dimension 2, due to Eisenbrand, Rote and Laue. The algorithm takes O(m + k) arithmetic operations, where m is the number of constraints and k is the maximum binary encoding length of the coefficients involved. This algorithm is believed to be optimal.

Item Type:Magistrali biennali
Corsi di Diploma di Laurea:Scuola di Scienze > Matematica
Uncontrolled Keywords:Integer programming, fixed dimension lattices
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:62633
Relatore:Conforti, Michelangelo
Data della tesi:05 July 2019
Biblioteca:Polo di Scienze > Biblioteca di Matematica
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:No

Solo per lo Staff dell Archivio: Modifica questo record