A geometrical bound for integer programming with polynomial constraints
Let F1, …, Fs ϵ Z[X1, …, Xn] be quasiconvex polynomials of degree bounded by d ≥ 2. Let L be an upper bound for the binary length of their coefficients. We show that the system F1 ≤ 0, …, Fs ≤ 0 admits an integer solution if and only if there exists such a solution with binary length bounded by (sd)...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | SER |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v529LNCS_n_p121_Bank |
| Aporte de: |
| id |
todo:paper_03029743_v529LNCS_n_p121_Bank |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_03029743_v529LNCS_n_p121_Bank2023-10-03T15:19:06Z A geometrical bound for integer programming with polynomial constraints Bank, B. Krick, T. Mandel, R. Solernó, P. Budach L. Bins Computation theory Integer solutions Minimization problems Quasiconvex polynomials Upper Bound Integer programming Let F1, …, Fs ϵ Z[X1, …, Xn] be quasiconvex polynomials of degree bounded by d ≥ 2. Let L be an upper bound for the binary length of their coefficients. We show that the system F1 ≤ 0, …, Fs ≤ 0 admits an integer solution if and only if there exists such a solution with binary length bounded by (sd)cn · L. (Here c > 0 is a constant independent on s, d, n and L). We obtain a similar geometric bound for the corresponding minimization problem. The simply exponential feature of our bound is intrinsic to this problem. © Springer-Verlag Berlin Heidelberg 1991. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v529LNCS_n_p121_Bank |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Bins Computation theory Integer solutions Minimization problems Quasiconvex polynomials Upper Bound Integer programming |
| spellingShingle |
Bins Computation theory Integer solutions Minimization problems Quasiconvex polynomials Upper Bound Integer programming Bank, B. Krick, T. Mandel, R. Solernó, P. Budach L. A geometrical bound for integer programming with polynomial constraints |
| topic_facet |
Bins Computation theory Integer solutions Minimization problems Quasiconvex polynomials Upper Bound Integer programming |
| description |
Let F1, …, Fs ϵ Z[X1, …, Xn] be quasiconvex polynomials of degree bounded by d ≥ 2. Let L be an upper bound for the binary length of their coefficients. We show that the system F1 ≤ 0, …, Fs ≤ 0 admits an integer solution if and only if there exists such a solution with binary length bounded by (sd)cn · L. (Here c > 0 is a constant independent on s, d, n and L). We obtain a similar geometric bound for the corresponding minimization problem. The simply exponential feature of our bound is intrinsic to this problem. © Springer-Verlag Berlin Heidelberg 1991. |
| format |
SER |
| author |
Bank, B. Krick, T. Mandel, R. Solernó, P. Budach L. |
| author_facet |
Bank, B. Krick, T. Mandel, R. Solernó, P. Budach L. |
| author_sort |
Bank, B. |
| title |
A geometrical bound for integer programming with polynomial constraints |
| title_short |
A geometrical bound for integer programming with polynomial constraints |
| title_full |
A geometrical bound for integer programming with polynomial constraints |
| title_fullStr |
A geometrical bound for integer programming with polynomial constraints |
| title_full_unstemmed |
A geometrical bound for integer programming with polynomial constraints |
| title_sort |
geometrical bound for integer programming with polynomial constraints |
| url |
http://hdl.handle.net/20.500.12110/paper_03029743_v529LNCS_n_p121_Bank |
| work_keys_str_mv |
AT bankb ageometricalboundforintegerprogrammingwithpolynomialconstraints AT krickt ageometricalboundforintegerprogrammingwithpolynomialconstraints AT mandelr ageometricalboundforintegerprogrammingwithpolynomialconstraints AT solernop ageometricalboundforintegerprogrammingwithpolynomialconstraints AT budachl ageometricalboundforintegerprogrammingwithpolynomialconstraints AT bankb geometricalboundforintegerprogrammingwithpolynomialconstraints AT krickt geometricalboundforintegerprogrammingwithpolynomialconstraints AT mandelr geometricalboundforintegerprogrammingwithpolynomialconstraints AT solernop geometricalboundforintegerprogrammingwithpolynomialconstraints AT budachl geometricalboundforintegerprogrammingwithpolynomialconstraints |
| _version_ |
1807315334882918400 |