Une borne optimale pour la programmation entière quasi-convexe
                - Consulter un extrait
 - Année : 1993
 - Fascicule : 2
 - Tome : 121
 - Format : Électronique
 - Langue de l'ouvrage :
Français - Class. Math. : 90~C~10, 65~K~05
 - Pages : 299-314
 - DOI : 10.24033/bsmf.2210
 
          Soient $F_1,\ldots ,F_s\in \mathbb {Z}[X_1,\ldots ,X_N]$ des polynômes quasiconvexes de degré majoré par $d\geq 2$, et $\ell $ une borne pour la longueur binaire de leurs coefficients. On montre que si le système $F_1\leq 0,\ldots ,F_s\leq 0$ admet une solution entière, alors il existe une telle solution à longueur binaire majorée par $(sd)^{cn} \ell $ (où $c$ est une constante, indépendante de $s,d,n$ et $\ell $). Le caractère simplement exponentiel de cette borne est intrinsèque au problème. On obtient aussi une borne similaire pour le problème de minimisation correspondant. 
        
                    
            