{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:54Z","timestamp":1725560274183},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_36","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:00:06Z","timestamp":1127815206000},"page":"409-421","source":"Crossref","is-referenced-by-count":0,"title":["Average-Case Non-approximability of Optimisation Problems"],"prefix":"10.1007","author":[{"given":"Birgit","family":"Schelm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","volume-title":"33rd FOCS","author":"S. Arora","year":"1992","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Hardness of Approximation Problems. In: 33rd FOCS, IEEE, Los Alamitos (1992)"},{"key":"36_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (1999)"},{"key":"36_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-79235-9","volume-title":"Structural Complexity I","author":"J. Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I, 2nd edn. Springer, Heidelberg (1995)","edition":"2"},{"key":"36_CR4","volume-title":"Complexity Theory \u2013 Current Research","author":"J. Belanger","year":"1993","unstructured":"Belanger, J., Wang, J.: On average-P vs. average-NP. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory \u2013 Current Research. Cambridge University Press, Cambridge (1993)"},{"key":"36_CR5","first-page":"151","volume":"50","author":"J. Belanger","year":"1995","unstructured":"Belanger, J., Wang, J.: On the NP-isomorphism with respect to random instances. JCSS\u00a050, 151\u2013164 (1995)","journal-title":"JCSS"},{"key":"36_CR6","first-page":"193","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. JCSS\u00a044, 193\u2013219 (1992)","journal-title":"JCSS"},{"key":"36_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-36494-3_20","volume-title":"STACS 2003","author":"H. Buhrman","year":"2003","unstructured":"Buhrman, H., Fortnow, L., Pavan, A.: Some results on derandomization. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 212\u2013222. Springer, Heidelberg (2003)"},{"key":"36_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/3-540-36494-3_43","volume-title":"20th STACS","author":"A. Coja-Oghlan","year":"2003","unstructured":"Coja-Oghlan, A., Taraz, A.: Colouring random graphs in expected polynomial time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 487\u2013498. Springer, Heidelberg (2003)"},{"issue":"5","key":"36_CR9","doi-asserted-by":"publisher","first-page":"1759","DOI":"10.1137\/S0097539796304220","volume":"28","author":"P. Crescenzi","year":"1999","unstructured":"Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L.: Structure in approximation classes. SIAM J. Comp.\u00a028(5), 1759\u20131782 (1999)","journal-title":"SIAM J. Comp."},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Panconesi, A.: Completeness in approximation classes. Inf. and Comp.\u00a093, 241\u2013262 (1991)","DOI":"10.1016\/0890-5401(91)90025-W"},{"key":"36_CR11","volume-title":"Theory of Computational Complexity","author":"D.-Z. Du","year":"2000","unstructured":"Du, D.-Z., Ko, K.: Theory of Computational Complexity. John Wiley & Sons, Chichester (2000)"},{"key":"36_CR12","volume-title":"32nd FOCS","author":"U. Feige","year":"1991","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating Clique is almost NP-complete. In: 32nd FOCS. IEEE, Los Alamitos (1991)"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D.: The complexity of near optimal graph coloring. J. ACM\u00a023, 43\u201349 (1976)","journal-title":"J. ACM"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. Grimmet","year":"1975","unstructured":"Grimmet, G., McDiarmid, C.: On colouring random graphs. Math. Proc. Camb. Phil. Soc.\u00a077, 313\u2013324 (1975)","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"36_CR15","volume-title":"28th FOCS","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Y.: Complete and incomplete randomized NP problems. In: 28th FOCS. IEEE, Los Alamitos (1987)"},{"key":"36_CR16","first-page":"346","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich, Y.: Average case completeness. JCSS\u00a042, 346\u2013398 (1991)","journal-title":"JCSS"},{"key":"36_CR17","volume-title":"10th Structure","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: 10th Structure. IEEE, Los Alamitos (1995)"},{"key":"36_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/BFb0055799","volume-title":"22nd MFCS","author":"J. K\u00f6bler","year":"1998","unstructured":"K\u00f6bler, J., Schuler, R.: Average-case intractability vs. worst-case intractability. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, p. 493. Springer, Heidelberg (1998)"},{"key":"36_CR19","first-page":"490","volume":"36","author":"M. Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problems. JCSS\u00a036, 490\u2013509 (1988)","journal-title":"JCSS"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"Kreuter, B., Nierhoff, T.: Greedily approximating the r-independent set and kcenter problems on random instances. In: Rand. and Approx. Techniques in Comp. Science, Springer, Heidelberg (1997)","DOI":"10.1007\/3-540-63248-4_4"},{"key":"36_CR21","volume-title":"16th STOC","author":"L. Levin","year":"1984","unstructured":"Levin, L.: Problems, complete in \u201caverage\u201d instance. In: 16th STOC. ACM, New York (1984)"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF01874388","volume":"1","author":"C. McDiarmid","year":"1984","unstructured":"McDiarmid, C.: Colouring random graphs. Ann. Operations Res.\u00a01, 183\u2013200 (1984)","journal-title":"Ann. Operations Res."},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Nickelsen, A., Schelm, B.: Average-case computations \u2013 Comparing AvgP, HP, and Nearly-P. In: CCC (2005) (to appear)","DOI":"10.1109\/CCC.2005.4"},{"key":"36_CR24","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"Schapire, R.: The emerging theory of average-case complexity. Technical Report MIT\/LCS\/TM-431, MIT Laboratory of Computer Science (1990)","DOI":"10.21236\/ADA222821"},{"key":"36_CR26","unstructured":"Schelm, B.: Average-Case Approximability of Optimisation Problems. Doctoral Thesis, TU Berlin, Fak. f. Elektrotechnik und Informatik (2004), http:\/\/edocs.tu-berlin.de\/diss\/2004\/schelmbirgit.pdf"},{"key":"36_CR27","unstructured":"Schindelhauer, C.: Average- und Median-Komplexit\u00e4tsklassen. Doctoral Thesis, Universit\u00e4t L\u00fcbeck (1996)"},{"key":"36_CR28","volume-title":"10th Structure","author":"R. Schuler","year":"1995","unstructured":"Schuler, R., Watanabe, O.: Toward average-case complexity analysis of NP optimization problems. In: 10th Structure. IEEE, Los Alamitos (1995)"},{"key":"36_CR29","volume-title":"Complexity Theory Retrospective II","author":"J. Wang","year":"1997","unstructured":"Wang, J.: Average-case computational complexity theory. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II. Springer, Heidelberg (1997)"},{"key":"36_CR30","volume-title":"Advances in Complexity and Algorithms","author":"J. Wang","year":"1997","unstructured":"Wang, J.: Average case intractable NP-problems. In: Du, D.-Z., Ko, K. (eds.) Advances in Complexity and Algorithms. Kluwer, Dordrecht (1997)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:12:25Z","timestamp":1605625945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11537311_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}