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)...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bank, B., Krick, T., Mandel, R., Solernó, P., Budach L.
Formato: SER
Materias:
Bins
Computation theory
Integer solutions
Minimization problems
Quasiconvex polynomials
Upper Bound
Integer programming
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v529LNCS_n_p121_Bank
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares