Une borne optimale pour la programmation entière quasi-convexe
- 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.