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: |
| Sumario: | 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. |
|---|