Navegar

Colección

Datos Estadísticas

Artículo

Bank, B.; Krick, T.; Mandel, R.; Solernó, P.; Budach L. "A geometrical bound for integer programming with polynomial constraints" (1991) 8th International Conference on Fundamentals of Computation Theory, FCT 1991. 529 LNCS:121-125
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:A geometrical bound for integer programming with polynomial constraints
Autor:Bank, B.; Krick, T.; Mandel, R.; Solernó, P.; Budach L.
Filiación:Humboldt Universität zu Berlin, Fachbereich Mathematik, PSF 1297, Berlin, O-1086, Germany
Working group Noaï Fitchas, Departamento de Matemáticas, Universidad de Buenos Aires, Ciudad Universitaria, Pab.I, (1428), Nuñez, Buenos Aires, Argentina
Palabras clave:Bins; Computation theory; Integer solutions; Minimization problems; Quasiconvex polynomials; Upper Bound; Integer programming
Año:1991
Volumen:529 LNCS
Página de inicio:121
Página de fin:125
DOI: http://dx.doi.org/10.1007/3-540-54458-5_56
Título revista:8th International Conference on Fundamentals of Computation Theory, FCT 1991
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v529LNCS_n_p121_Bank

Referencias:

  • Bank, B., Mandel, R., (1988) Parametric integer optimization, , Akademie-Verlag, Berlin
  • Bank, B., Mandel, R., (1988) (Mixed-)Integer solutions of quasiconvex polynomial inequalities, 45, pp. 20-34. , Mathematical Research Advances in Mathematical Optimization, Akademie-Verlag, Berlin
  • Heintz, J., Roy, M.-F., Solernó, P., (1989) On the complexity of semialgebraic sets, pp. 293-298. , (extended abstract), Proc. IFIP 89, IX World Computer Congress, North Holland
  • Heintz, J., Roy, M.-F., Solernó, P., (1989) Complexité du principe de Tarski-Seidenberg, pp. 825-830. , C. R. Acad. Sci. Paris, t.309, Serie I
  • Heintz, J., Roy, M.-F., Solernó, P., (1990) Sur la complexité du principe de Tarski-Seidenberg, 118, pp. 101-126. , Bull. Soc. math. France
  • Khachiyan, L.G., (1983) Convexity and complexity in polynomial programming, , Proc. Int. Congress Math., Varsaw
  • Renegar, J., (1989) On the computational complexity and geometry of the first-order theory of the reals. Part III. Quantifier Elimination, 856. , Technical report, Cornell University
  • Schrijver, A., (1986) Theory of linear and integer programming, , Wiley Interscience Series in Discrete Mathematics
  • Solernó, P., (1989) Complejidad de conjuntos semialgebraicos, , Thesis, Universidad de Buenos Aires
  • Tarasov, S.P., Khachiyan, L.G., (1980) Bounds of solutions and algorithmic complexity of systems of convex diophantine inequalities, 22 (3). , Soviet.Math. AdelA4 -

Citas:

---------- APA ----------
Bank, B., Krick, T., Mandel, R., Solernó, P. & Budach L. (1991) . A geometrical bound for integer programming with polynomial constraints. 8th International Conference on Fundamentals of Computation Theory, FCT 1991, 529 LNCS, 121-125.
http://dx.doi.org/10.1007/3-540-54458-5_56
---------- CHICAGO ----------
Bank, B., Krick, T., Mandel, R., Solernó, P., Budach L. "A geometrical bound for integer programming with polynomial constraints" . 8th International Conference on Fundamentals of Computation Theory, FCT 1991 529 LNCS (1991) : 121-125.
http://dx.doi.org/10.1007/3-540-54458-5_56
---------- MLA ----------
Bank, B., Krick, T., Mandel, R., Solernó, P., Budach L. "A geometrical bound for integer programming with polynomial constraints" . 8th International Conference on Fundamentals of Computation Theory, FCT 1991, vol. 529 LNCS, 1991, pp. 121-125.
http://dx.doi.org/10.1007/3-540-54458-5_56
---------- VANCOUVER ----------
Bank, B., Krick, T., Mandel, R., Solernó, P., Budach L. A geometrical bound for integer programming with polynomial constraints. Lect. Notes Comput. Sci. 1991;529 LNCS:121-125.
http://dx.doi.org/10.1007/3-540-54458-5_56