×

zbMATH — the first resource for mathematics

An optimal bound for quasiconvex integer programming. (Une borne optimale pour la programmation entière quasi-convexe.) (French) Zbl 0777.90034
Summary: Let \(F_ 1,\dots,F_ s\in\mathbb{Z}[X_ 1,\dots,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,\dots,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 minimization problem.
MSC:
90C10 Integer programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] BANK (B.) and MANDEL (R.) . - Parametric integer optimization . - Akademie-Verlag, Berlin, 1988 . MR 89m:90119 | Zbl 0643.90043 · Zbl 0643.90043
[2] BANK (B.) and MANDEL (R.) . - (Mixed-)Integer solutions of quasiconvex polynomial inequalities , Math. Res., t. 45, 1988 , p. 20-34. MR 89i:90088 | Zbl 0657.90071 · Zbl 0657.90071
[3] HEINTZ (J.) , ROY (M.-F.) and SOLERNÓ (P.) . - On the complexity of semialgebraic sets (Extended abstract) , Proc. IFIP Congress’89, IX World Computer Congress, North-Holland, 1989 , p. 293-298.
[4] HEINTZ (J.) , ROY (M.-F.) et SOLERNÓ (P.) . - Complexité du principe de Tarski-Seidenberg , C. R. Acad. Sci. Paris Sér. I Math., t. 309, 1989 , p. 825-830. MR 92c:12012 | Zbl 0704.03013 · Zbl 0704.03013
[5] HEINTZ (J.) , ROY (M.-F.) et SOLERNÓ (P.) . - Sur la complexité du principe de Tarski-Seidenberg , Bull. Soc. Math. France, t. 118, 1990 , p. 101-126. Numdam | MR 92g:03047 | Zbl 0767.03017 · Zbl 0767.03017
[6] KHACHIYAN (L.G.) . - Convexity and complexity in polynomial programming . - Proc. Int. Congress Math., Varsovie, 1983 , p. 1569-1577. MR 87a:90097 | Zbl 0588.90070 · Zbl 0588.90070
[7] KRICK (T.) . - Complejidad para problems de geometría elemental , Thèse, Université de Buenos Aires, 1990 .
[8] MIGNOTTE (M.) . - Mathématiques pour le calcul formel . - P.U.F, 1989 . MR 91a:68001 | Zbl 0679.12001 · Zbl 0679.12001
[9] RENEGAR (J.) . - On the computational complexity and geometry of the first order theory of the reals , Part III, Quantifier elimination, I. Symbolic Computation, t. 13, 1992 , p. 329-352. MR 93h:03011c | Zbl 0798.68073 · Zbl 0798.68073
[10] ROCKAFELLAR (R.T.) . - Convex Analysis . - Princeton Mathematical Series 28, 1970 . MR 43 #445 | Zbl 0193.18401 · Zbl 0193.18401
[11] SCHRIJVER (A.) . - Theory of linear and integer programming . - Wiley Interscience Series in Discrete Mathematics, 1989 . · Zbl 0673.05027
[12] SOLERNÓ (P.) . - Complejidad de conjuntos semialgebraicos , Thèse, Université de Buenos Aires, 1989 .
[13] TARASOV (S.P.) and KHACHIYAN (L.G.) . - Bounds of solutions and algorithmic complexity of systems of convex diophantine inequalities , Soviet. Math. Dokl., t. 22, 3, 1980 , p. 700-704. Zbl 0467.90048 · Zbl 0467.90048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.