{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:44Z","timestamp":1725456164746},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600176"},{"type":"electronic","value":"9783540494041"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022258","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T06:12:29Z","timestamp":1132639949000},"page":"217-227","source":"Crossref","is-referenced-by-count":0,"title":["Log-approximable minimization problems on random inputs"],"prefix":"10.1007","author":[{"given":"Anders","family":"Malmstr\u00f6m","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"16_CR1","unstructured":"N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1991."},{"key":"16_CR2","series-title":"volume 702 of LNCS","first-page":"43","volume-title":"Selected Papers","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. In E. B\u00f6rger, G. J\u00e4ger, H. Kleine B\u00fcning, S. Martini, and M.M. Richter, editors, Computer Science Logic, 6th Workshop, CSL '92, San Miniato 1992, Selected Papers, volume 702 of LNCS, pages 43\u201360. Springer-Verlag, 1993."},{"key":"16_CR3","unstructured":"P. Crescenzi and V. Kann. A compendium of NP optimization problems. unpublished, 1994."},{"key":"16_CR4","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43\u201373, 1974."},{"key":"16_CR5","series-title":"volume 832 of LNCS","first-page":"139","volume-title":"Selected Papers","author":"E. Gr\u00e4del","year":"1994","unstructured":"E. Gr\u00e4del and A. Malmstr\u00f6m. Approximable minimization problems and optimal solutions on random input. In E. B\u00f6rger, Y. Gurevich, and K. Meinke, editors, Computer Science Logic, 7th Workshop, CSL '93, Swansea 1993, Selected Papers, volume 832 of LNCS, pages 139\u2013149. Springer-Verlag, 1994."},{"key":"16_CR6","volume-title":"PhD thesis","author":"V. Kann","year":"1992","unstructured":"V. Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis, Royal Institute of Technology, Stockholm, 1992."},{"key":"16_CR7","volume-title":"Technical Report CRL-90-48","author":"P. Kolaitis","year":"1990","unstructured":"Ph. Kolaitis and M. Thakur. Logical definability of NP-optimization problems. Technical Report CRL-90-48, University of California, Santa Cruz, October 1990."},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Ph. Kolaitis and M. Thakur. Approximation properties of NP minimization classes. In Proc. 6th IEEE Symp. on Structure in Complexity Theory, pages 353\u2013366, 1991.","DOI":"10.1109\/SCT.1991.160280"},{"key":"16_CR9","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 logics and 0\u20131 laws. Information and Computation, 98:258\u2013294, 1992.","journal-title":"Information and Computation"},{"key":"16_CR10","first-page":"286","volume-title":"Proc. 25th ACM Symp. on Theory of Computing","author":"C. Lund","year":"1993","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proc. 25th ACM Symp. on Theory of Computing, pages 286\u2013293, New York, 1993. ACM."},{"key":"16_CR11","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximization and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,5]],"date-time":"2019-02-05T06:48:49Z","timestamp":1549349329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0022258","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}