{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:39:33Z","timestamp":1725496773448},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653851"},{"type":"electronic","value":"9783540493815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49381-6_46","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T06:47:50Z","timestamp":1196664470000},"page":"438-446","source":"Crossref","is-referenced-by-count":0,"title":["The Inapproximability of Non NP-hard Optimization Problems"],"prefix":"10.1007","author":[{"given":"Liming","family":"Cai","sequence":"first","affiliation":[]},{"given":"David","family":"Juedes","sequence":"additional","affiliation":[]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,3,29]]},"reference":[{"key":"46_CR1","unstructured":"Arora, S.: Personal Communication."},{"key":"46_CR2","unstructured":"Arora, S., Lund, C.: Hardness of Approximations. In Approximation Algorithms for NP-hard problems. Ed. Dorit Hochbaum. (1997)."},{"key":"46_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Verification and hardness of approximation problems. Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science. (1992) 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs. Proceedings of the 33rd IEEE Annual Symposium on Foundations of Computer Science. (1992) 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"46_CR5","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. F. Buss","year":"1993","unstructured":"Buss, J. F., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing. 22 (1993) 560\u2013572.","journal-title":"SIAM Journal on Computing"},{"key":"46_CR6","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistic checking of proofs and applications to approximation. Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (1993) 113\u2013131."},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/S0097539793258295","volume":"26","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing. 26 (1997) 733\u2013750","journal-title":"SIAM Journal on Computing."},{"key":"46_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On Fixed-Parameter Tractability and Approximability of NP Optimization Problems. Journal of Computer and System Sciences. 54 (1997) 465\u2013474.","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR9","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/inco.1995.1156","volume":"123","author":"L. Cai","year":"1995","unstructured":"Cai, L., Chen, J., Downey, R., Fellows, M.: On the Structure of Parameterized Problems in NP. Information and Computation. 123 (1995) 38\u201349.","journal-title":"Information and Computation"},{"key":"46_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF02090764","volume":"23","author":"J. D\u00edaz","year":"1990","unstructured":"D\u00edaz, J., Tor\u00e1n, J.: Classes of bounded nondeterminism. Math. System Theory. 23 (1990) 21\u201332.","journal-title":"Math. System Theory"},{"key":"46_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Fixed-Parameter Intractability. Proceedings of the 7th IEEE Annual Conference on Structure in Complexity Theory. (1992) 36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM Journal on Computing. 24 (1995) 873\u2013921.","journal-title":"SIAM Journal on Computing"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Parameterized Computational Feasibility. The Proceedings of FEASMATH: Feasible Mathematics: A Mathematical Sciences Institute Workshop (1995).","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"46_CR14","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/BF01178668","volume":"31","author":"G. Farr","year":"1994","unstructured":"Farr, G.: On problems with short certificates. Acta Informatica. 31 (1994) 479\u2013502.","journal-title":"Acta Informatica"},{"key":"46_CR15","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. Proceedings of The 28th Annual ACM Symposium On The Theory Of Computing. (1996) 314\u2013318."},{"key":"46_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy M.: Approximating clique is almost NP-complete. Proceedings of the 32nd IEEE Symposium on the Foundations of Computer Science. (1991) 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"46_CR17","unstructured":"Feige, U., Kilian, J.: On Limited versus Polynomial Nondeterminism. CJTCS: Chicago Journal of Theoretical Computer Science. (1997)."},{"key":"46_CR18","unstructured":"Fotakis, D., Spirakis, P.: (poly(loglogn), poly(loglogn))-Restricted Verifiers are Unlikely to exist for languages in NP. Proceedings of the 23nd International Symposium on Mathematical Foundations of Computer Science. (1996) 360\u2013371."},{"key":"46_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/235767.235769","volume":"27","author":"J. Goldsmith","year":"1996","unstructured":"Goldsmith J., Levy, M., Mundhenk, M.: Limited Nondeterminism. SIGACT News. 27 (1996) 20\u201329.","journal-title":"SIGACT News"},{"key":"46_CR20","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(92)90052-E","volume":"13","author":"D. S. Johnson","year":"1992","unstructured":"Johnson, D. S.: The NP-Completeness Column: Ongoing Guide. Journal of Algorithms. 13 (1992) 502\u2013524.","journal-title":"Journal of Algorithms"},{"key":"46_CR21","unstructured":"Kann, V.: On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden. Ph.D. Thesis (1992)."},{"key":"46_CR22","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0304-3975(88)90131-4","volume":"61","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Vishkin, U.: On Finding a Minimum Dominating Set in a Tournament. Theoretical Computer Science. 61 (1988) 307\u2013316.","journal-title":"Theoretical Computer Science"},{"key":"46_CR23","doi-asserted-by":"crossref","unstructured":"Papadimitriou C. H., Yannakakis M.: On Limited Nondeterminism and the Complexity of the V-C Dimension. Proceedings of the 8th Annual Conference on Structure in Complexity Theory. (1993) 12\u201318.","DOI":"10.1109\/SCT.1993.336545"},{"key":"46_CR24","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M. J.: Relations Among Complexity Measures. Journal of the ACM. 26 (1979) 361\u2013381.","journal-title":"Journal of the ACM"},{"key":"46_CR25","doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D. A.: Nearly-linear Size Holographic Proofs. Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. (1994) 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"46_CR26","series-title":"Technical Report","volume-title":"\u03b2k-complete problems and greediness","author":"R. Szelepcs\u00e9nyi","year":"1993","unstructured":"Szelepcs\u00e9nyi, R.: \u03b2\n                           k-complete problems and greediness. Computer Science Department, University, Rochester, New York. Technical Report 445 (1993)."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49381-6_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T04:32:32Z","timestamp":1551155552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49381-6_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653851","9783540493815"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-49381-6_46","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}