{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:08Z","timestamp":1725460028384},"publisher-location":"Berlin\/Heidelberg","reference-count":12,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540582770"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0049329","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:58:16Z","timestamp":1141671496000},"page":"139-149","source":"Crossref","is-referenced-by-count":1,"title":["Approximable minimization problems and optimal solutions on random inputs"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anders","family":"Malmstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1991","unstructured":"N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1991."},{"key":"10_CR2","first-page":"43","volume-title":"Selected Papers, vol. 702 of LNCS","author":"T. Behrendt","year":"1993","unstructured":"Th. Behrendt, K. Compton and E. Gr\u00e4del, Optimization Problems: Expressibility, Approximation Properties, and Expected Asymptotic Growth of Optimal Solutions, Computer Science Logic, 6th Workshop, CSL '92, San Miniato 1992, Selected Papers, vol. 702 of LNCS, Springer-Verlag, 1993, pp. 43\u201360."},{"key":"10_CR3","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs, Academic Press, London, 1985."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"K. Compton, 0-1 laws in logic and combinatorics, in NATO Adv. Study Inst. on Algorithms and Order, I. Rival, ed., D. Reidel, 1988, pp. 353\u2013383.","DOI":"10.1007\/978-94-009-2639-4_10"},{"key":"10_CR5","unstructured":"K. Compton and E. Gr\u00e4del, Logical definability of counting functions, submitted for publication."},{"key":"10_CR6","first-page":"43","volume-title":"SIAM-AMS Proc.","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized first-order spectra and polynomial time recognizable sets, in complexity of Computations, R. Karp, ed., vol. 7 of SIAM-AMS Proc., Providence, RI, 1974, American Math. Soc., pp. 43\u201373."},{"key":"10_CR7","volume-title":"Technical Report UCSC-CRL-90-48","author":"P. Kolaitis","year":"1990","unstructured":"Ph. Kolaitis and M. Thakur, Logical definability of NP optimization problems, Technical Report UCSC-CRL-90-48, Computer and Information Sciences, University of California, Santa Cruz (1990), to appear in Information and Computation"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Thakur, Approximation properties of NP minimization classes, Proceedings of 6th IEEE Conference on Structure in Complexity Theory (1991), 353\u2013366, to appear in Journal of Computer and System Sciences.","DOI":"10.1109\/SCT.1991.160280"},{"key":"10_CR9","first-page":"446","volume-title":"The decision problem for probabilities of higher order properties","author":"P. Kolaitis","year":"1990","unstructured":"Ph. Kolaitis and M. Vardi, The decision problem for probabilities of higher order properties, in Proc. 19th ACM Symp. on Theory of Computing, New York, 1990, Association for Computing Machinery, pp. 446\u2013456."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. Kolaitis","year":"1992","unstructured":"Ph. Kolaitis and M. Vardi, Infinitary logic and 0-1 laws, Information and Computation 98 (1992), 258\u2013294.","journal-title":"Information and Computation"},{"key":"10_CR11","first-page":"327","volume-title":"Selected Papers, vol. 702 of LNCS","author":"C. Lautemann","year":"1993","unstructured":"C. Lautemann, Logical Definability of NP-Optimization Problems with Monadic Auxiliary Predicates, Computer Science Logic, 6th Workshop, CSL '92, San Miniato 1992, Selected Papers, vol. 702 of LNCS, Springer-Verlag, 1993, pp. 327\u2013339."},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Ch. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity, Journal of Computer and System Sciences 43 (1991), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049329.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:55:41Z","timestamp":1607550941000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540582770"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0049329","relation":{},"subject":[]}}