{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:01:58Z","timestamp":1725483718684},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_22","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:20:53Z","timestamp":1178356853000},"page":"286-300","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Integer Programming in the Blum-Shub-Smale Computational Model"],"prefix":"10.1007","author":[{"given":"Valentin E.","family":"Brimkov","sequence":"first","affiliation":[]},{"given":"Stefan S.","family":"Dantchev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"22_CR1","unstructured":"Ben-Or, M.: Lower Bounds for Algebraic Computation Tree. Proc. Of the 15th ACM STOC (1983) 80\u201386"},{"key":"22_CR2","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1995","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer-Verlag, Berlin Heidelberg New York (1995)"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines. Bull. Amer. Math. Soc. (NS), 21 (1989) 1\u201346","journal-title":"Bull. Amer. Math. Soc. (NS)"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1006\/jcom.1997.0446","volume":"13","author":"V.E. Brimkov","year":"1997","unstructured":"Brimkov, V.E., Danchev, S.S.: Real Data-Integer Solution Problems within the Blum-Shub-Smale Computational Model: J. of Complexity, 13 (1997) 279\u2013300","journal-title":"J. of Complexity"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s100920050026","volume":"36","author":"V.E. Brimkov","year":"1999","unstructured":"Brimkov, V.E., Danchev, S.S., Leoncini, M.: Tight Complexity Bounds for the Two-Dimensional Real Knapsack Problem. Calcolo, 36 (1999) 123\u2013128","journal-title":"Calcolo"},{"key":"22_CR6","unstructured":"Brimkov, V.E., Dantchev, S.S.: Lower Bounds, \u201cPseudopolynomial\u201d and Approximation Algorithms for the Knapsack Problem with Real Coefficients. Electronic Colloquium on Computational Complexity, TR98-015 (1998). \n                    \n                      http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0304-3975(96)00002-3","volume":"161","author":"F. Cucker","year":"1996","unstructured":"Cucker, F., Shub, M.: Generalized Knapsack Problem and Fixed Degree Separations. Theoret. Comput. Sci., 161 (1996) 301\u2013306","journal-title":"Theoret. Comput. Sci"},{"key":"22_CR8","volume-title":"a Guide to the Theory of NP-Completeness","author":"M.S. Garey","year":"1979","unstructured":"Garey, M.S., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman & Co., San Francisco (1979)"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J. Hastad","year":"1989","unstructured":"Hastad, J., Just, B., Lagarias, J.C., Schnoor, C.P.: Polynomial Time Algorithms for Finding Integer Relations among Real Numbers. SIAM J. Comput., 18 (1989) 859\u2013881","journal-title":"SIAM J. Comput"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0208040","volume":"8","author":"R. Kannan","year":"1979","unstructured":"Kannan, R., Bachem, A.: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM J. Comput., 8 (1979) 499\u2013507","journal-title":"SIAM J. Comput"},{"key":"22_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/3-540-63890-3_42","volume-title":"Proc. 8th ISAAC Symposium","author":"H. Kellerer","year":"1997","unstructured":"Kellerer, H., Mansini, R., Pferschy, U., Speranza, M.G.: An Efficient Fully Polynomial Approximation Scheme for the Subset-Sum Problem. Proc. 8th ISAAC Symposium, Lecture Notes in Computer Science, Vol. 1350. Springer-Verlag, Berlin Heidelberg New York (1997) 394\u2013403"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer Programming with a Fixed Number of Variables. Math. Oper. Res., 8 (1983) 538\u2013548","journal-title":"Math. Oper. Res"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Jr., Lov\u00e1sz, L.: Factoring Polynomials with Rational Coefficients. Math. Ann., 261 (1982) 515\u2013534","journal-title":"Math. Ann"},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer Auf Der Heide","year":"1984","unstructured":"Meyer Auf Der Heide, F.: A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem. J. of ACM, 31 (3) (1984) 668\u2013676","journal-title":"J. of ACM"},{"key":"22_CR15","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester New York Brisbane Toronto Singapore (1990)"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear Programming in Linear Time when the Dimension is Fixed. J. of ACM, 31 (1) (1984) 114\u2013127","journal-title":"J. of ACM"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01270397","volume":"4","author":"J.L. Monta\u00f1a","year":"1993","unstructured":"Monta\u00f1a, J.L., Pardo, L.M.: Lower Bounds for Arithmetic Networks. Appl. Algebra Eng. Comm. Comput., 4 (1993) 1\u201324","journal-title":"Appl. Algebra Eng. Comm. Comput"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/jcom.1995.1002","volume":"11","author":"E. Novak","year":"1994","unstructured":"Novak, E., The Real Number Model in Numerical Analysis. J. of Complexity, 11 (1994) 57\u201373","journal-title":"J. of Complexity"},{"key":"22_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Springer-Verlag, Berlin Heidelberg New York (1985)"},{"key":"22_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/3-540-61310-2_3","volume-title":"Integer Programming and Combinatorial Optimization","author":"C. R\u00f6ssner","year":"1996","unstructured":"R\u00f6ssner, C., Schnorr, C.P.: An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension. In: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1084. Springer-Verlag, Berlin Heidelberg New York (1996) 31\u201343"},{"key":"22_CR21","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming, Wiley, Chichester New York Brisbane Toronto Singapore (1986)"},{"key":"22_CR22","first-page":"633","volume-title":"Handbook of Theoretical Computer Science","author":"V. Strassen","year":"1990","unstructured":"Strassen, V.: Algebraic Complexity Theory. In: van Leeuwen, J. (Ed.): Handbook of Theoretical Computer Science, Vol. A Elsevier, Amsterdam (1990) 633\u2013672"},{"issue":"2","key":"22_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/1032043","volume":"32","author":"S. Smale","year":"1990","unstructured":"Smale, S.: Some Remarks on the Foundations of Numerical Analysis. SIAM Rev., 32 (2) (1990) 211\u2013220","journal-title":"SIAM Rev"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T09:52:26Z","timestamp":1550310746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}