{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T15:01:09Z","timestamp":1784127669864,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662242","type":"print"},{"value":"9783540485230","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_17","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"200-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":126,"title":["On Some Tighter Inapproximability Results (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"N. Alon, U. Feige, A. Wigderson and D. Zuckerman, Derandomized Graph Products, Computational Complexity 5 (1995), pp. 60\u201375.","journal-title":"Computational Complexity"},{"key":"17_CR2","unstructured":"S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems, Ph. D. Thesis, UC Berkeley, 1994; available as TR94-476 at ftp:\/\/ftp.cs.princeton.edu"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Hardness of Approximation Problems, Proc. 33rd IEEE FOCS (1992), pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"V. Bafna and P. Pevzner, Genome rearrangements and sorting by reversals, SIAM J. on Computing 25 (1996), pp. 272\u2013289.","journal-title":"SIAM J. on Computing"},{"key":"17_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Proc. 4thWorkshop on Algorithms and Data Structures","author":"P. Berman","year":"1995","unstructured":"P. Berman and T. Fujito, Approximating Independent Sets in Degree 3 Graphs, Proc. 4thWorkshop on Algorithms and Data Structures, LNCS Vol. 955, Springer-Verlag, 1995, pp. 449\u2013460."},{"key":"17_CR6","unstructured":"P. Berman and M. F\u00fcrer, Approximating Maximum Independent Set in Bounded Degree Graphs, Proc. 5th ACM-SIAM SODA (1994), pp. 365\u2013371."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"P. Berman and S. Hannenhali, Fast Sorting by Reversals, Proc. 7th Symp. on Combinatorial Pattern Matching, 1996, pp. 168\u2013185.","DOI":"10.1007\/3-540-61258-0_14"},{"key":"17_CR8","unstructured":"P. Berman and M. Karpinski, On Some Tighter Inapproximbility Results, preliminary version appeared in ECCC TR98-065, the full version available under http:\/\/theory.cs.uni-bonn.de\/_marek."},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger, On the Complexity of Approximating the Independent Set Problem, Information and Computation 96 (1992), pp. 77\u201394.","journal-title":"Information and Computation"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, Extremal Graph Theory, 1978, Academic Press.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"A. Caprara, Sorting by reversals is difficult, Proc. 1st ACM RECOMB (Int. Conf. on Computational Molecular Biology), 1997, pp. 75\u201383.","DOI":"10.1145\/267521.267531"},{"key":"17_CR12","unstructured":"D.A. Christie, A 3\/2-Approximation Algorithm for Sorting by Reversals, Proc. 9th ACM-SIAM SODA (1998), pp. 244\u2013252."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"D. Cohen and M. Blum, Improved Bounds for Sorting Burnt Pancakes, Discrete Applied Mathematics, Vol. 61, pp. 105\u2013125.","DOI":"10.1016\/0166-218X(94)00009-3"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"P. Crescenzi and V. Kann, A Compendium of NP Optimization Problems, Manuscript, 1997; available at http:\/\/www.nada.kth.se\/theory\/problemlist.html","DOI":"10.1007\/3-540-63248-4_10"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Goemans, Approximating the Value of Two Prover Proof Systems with Applications to MAX-2SAT and MAX-DICUT, Proc. 3rd Israel Symp. on Theory of Computing and Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W.H. Gates","year":"1979","unstructured":"W.H. Gates, and C.H. Papadimitriou, Bounds for Sorting by Prefix Reversals, Discrete Mathematics 27 (1979), pp. 47\u201357.","journal-title":"Discrete Mathematics"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"M. Goemans and D. Williamson, 878-Approximation Algorithms for MAX CUT and MAX 2SAT, Proc. 26th ACM STOC (1994), pp. 422\u2013431.","DOI":"10.1145\/195058.195216"},{"key":"17_CR18","unstructured":"J. H\u00e5stad, Clique is Hard to Approximate within n1-\u03b5, Proc. 37th IEEE FOCS (1996), pp. 627\u2013636."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal Inapproximability results, Proc. 29th ACMSTOC, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"S. Hannenhali and P. Pevzner, Transforming Cabbage into Turnip (Polynomial time algorithm for sorting by reversals), Proc. 27th ACM STOC (1995), pp. 178\u2013187.","DOI":"10.1145\/225058.225112"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"H. Kaplan, R. Shamir and R.E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proc. 8th ACM-SIAM SODA, 1997, pp. 344\u2013351.","DOI":"10.1145\/267521.267544"},{"key":"17_CR22","first-page":"425","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, JCSS 43, 1991, pp. 425\u2013440.","journal-title":"JCSS"},{"key":"17_CR23","unstructured":"L. Trevisan, G. Sorkin, M. Sudan and D. Williamson, Gadgets, Approximation and Linear Programming, Proc. 37th IEEE FOCS (1996), pp. 617\u2013626."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T13:50:20Z","timestamp":1737640220000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}