{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:29Z","timestamp":1725664469915},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615811"},{"type":"electronic","value":"9783540706328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61581-4_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:02:14Z","timestamp":1330275734000},"page":"307-322","source":"Crossref","is-referenced-by-count":5,"title":["The complexity of approximate optima for greatest common divisor computations"],"prefix":"10.1007","author":[{"given":"Carsten","family":"R\u00f6ssner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Pierre","family":"Seifert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"29_CR1","first-page":"167","volume":"17","author":"J. M. Anthonisse","year":"1973","unstructured":"J. M. Anthonisse. A note on equivalent systems of linear diophantine equations. Z. Operations Research, Volume 17, pages 167\u2013177, 1973.","journal-title":"Z. Operations Research"},{"key":"29_CR2","volume-title":"Ph.D. thesis","author":"S. Arora","year":"1994","unstructured":"S. Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems. Ph.D. thesis, University of California at Berkeley, 1994."},{"doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern and Z Sweedyk. The hardness of approximate optima in lattices, codes and systems of linear equations. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 724\u2013730, 1993.","key":"29_CR3","DOI":"10.1109\/SFCS.1993.366815"},{"unstructured":"S. Arora and C. Lund. Hardness of approximation. In D. Hochbaum (editor), Approximation Algorithms for NP-hard Problems, Chapter 11. PWS Publishing, 1996.","key":"29_CR4"},{"key":"29_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"G. Ausiello, P. Crescenzi and M. Protasi. Approximate solutions of NP optimization problems. Theoretical Computer Science, Volume 150, pages 1\u201355, 1995.","journal-title":"Theoretical Computer Science"},{"key":"29_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1978","unstructured":"V. Chvatal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, Volume 4, pages 233\u2013235, 1978.","journal-title":"Mathematics of Operations Research"},{"doi-asserted-by":"crossref","unstructured":"U. Feige. A threshold of In n for approximating set cover. In Proc. 28th ACM Symp. Theory of Computing, 1996.","key":"29_CR7","DOI":"10.1145\/237814.237977"},{"doi-asserted-by":"crossref","unstructured":"U. Feige and L. Lov\u00e1sz. Two-prover one-round proof systems: Their power and their problems. In Proc. 24th ACM Symp. Theory of Computing, pages 643\u2013654, 1992.","key":"29_CR8","DOI":"10.1145\/129712.129783"},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1137\/0218059","volume":"18","author":"J. H\u00e5stad","year":"1989","unstructured":"J. H\u00e5stad, B. Just, J. C. Lagarias and C. P. Schnorr. Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Computation, Volume 18, pages 859\u2013881, 1989.","journal-title":"SIAM J. Computation"},{"key":"29_CR10","first-page":"256","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson. Approximation algorithms for combinatorial algorithms. J. CSS, Volume 9, pages 256\u2013278, 1974.","journal-title":"J. CSS"},{"key":"29_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1145\/322358.322368","volume":"30","author":"R. Kannan","year":"1983","unstructured":"R. Kannan. Polynomial-time aggregation of integer programming problems. J. ACM, Volume 30, pages 133\u2013145, 1983.","journal-title":"J. ACM"},{"key":"29_CR12","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher (editors), Complexity of Computer Computations. Plenum Press, New York, 1972."},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of minimization problems. J. ACM, Volume 41, pages 960\u2013981, 1994.","journal-title":"J. ACM"},{"key":"29_CR14","volume-title":"The Theory of Error-Correcting Codes","author":"F. J. Mac Williams","year":"1977","unstructured":"F. J. Mac Williams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North Holland, Amsterdam, 1977."},{"doi-asserted-by":"crossref","unstructured":"B. S. Majewski and G. Havas. The complexity of greatest common divisor computations. In Proc. 1st International Symposium on Algorithmic Number Theory, pages 184\u2013193. Springer, 1994. LNCS 877.","key":"29_CR15","DOI":"10.1007\/3-540-58691-1_56"},{"doi-asserted-by":"crossref","unstructured":"R. Raz. A parallel repetition theorem. In Proc. 27th ACM Symp. Theory of Computing, pages 447\u2013456, 1995.","key":"29_CR16","DOI":"10.1145\/225058.225181"},{"unstructured":"P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math. Inst., University of Amsterdam, 1981.","key":"29_CR17"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Number Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61581-4_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:08:24Z","timestamp":1605629304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61581-4_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615811","9783540706328"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-61581-4_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}