SMF

Une borne optimale pour la programmation entière quasi-convexe

Bernd Bank, Joos Heintz, Teresa Krick, Reinhard Mandel, Pablo Solernó
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.
Let $F_1,\ldots , F_s\in \mathbb {Z}[X_1,\ldots ,X_n]$ be quasiconvex polynomials of degrees bounded by $d\geq 2$ and assume that the maximum binary length of the coefficients of these polynomials doesn't exceed a given natural number $\ell $. We show that the system of polynomial inequalities $F_1\leq 0,\ldots ,F_s\leq 0$ admits an integer solution if and only if such a solution with binary length bounded by $(sd)^{cn}\ell $ exists. (Here $c$ is a constant, independent on $s,d,n$ and $\ell $). The simply exponential nature of this bound is intrinsical to this problem. We obtain a similar geometrical bound for the corresponding minimisation problem.


Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...