{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T07:07:45Z","timestamp":1743145665222,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18173-8_28","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"377-389","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Block Sorting Is APX-Hard"],"prefix":"10.1007","author":[{"given":"N. S.","family":"Narayanaswamy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swapnoneel","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"issue":"2","key":"28_CR1","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by Transpositions. SIAM Journal of Discrete Mathematics 11(2), 224\u2013240 (1998)","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"8\u201310","key":"28_CR2","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.tcs.2008.10.022","volume":"410","author":"WW Bein","year":"2009","unstructured":"Bein, W.W., Larmore, L.L., Latifi, S., Sudborough, I.H.: A Quadratic TIme 2-Approximation Algorithm for Block Sorting. Theoretical Computer Science 410(8\u201310), 711\u2013717 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"28_CR3","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1142\/S0129054103001820","volume":"14","author":"WW Bein","year":"2003","unstructured":"Bein, W.W., Larmore, L.L., Latifi, S., Sudborough, I.H.: Block sorting is hard. International Journal of Foundations of Computer Science 14(3), 425\u2013437 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"28_CR4","first-page":"654","volume":"6755","author":"L Bulteau","year":"2011","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Sorting by Transpositions is Difficult. Automata, Languages and Programming 6755, 654\u2013665 (2011)","journal-title":"Automata, Languages and Programming"},{"key":"28_CR5","unstructured":"Christie, D.A.: Genome Rearrangement Problems. PhD Thesis, University of Glasgow (1999)"},{"issue":"4","key":"28_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I Elias","year":"2006","unstructured":"Elias, I., Hartman, T.: A 1.375-Approximation Algorithm for Sorting by Transpositions. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 3(4), 369\u2013379 (2006). doi:10.1109\/TCBB.2006.44","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"28_CR7","unstructured":"Gobi, R., Latifi, S., Bein, W.W.: Adaptive Sorting Algorithms for Evaluation of Automatic Zoning Employed in OCR Devices. In: Proceedings of the 2000 International Conference on Imaging Science, Systems, and Technology, CISST 2000, pp. 253\u2013259. CSREA Press (2000)"},{"issue":"4","key":"28_CR8","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some Optimal Inapproximability Results. Journal of the ACM 48(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Rama, R., Raman, V., Vijayakumar, S.: Merging and Sorting ByStrip Moves. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 314\u2013325. Springer, Heidelberg (2003)","DOI":"10.1007\/978-3-540-24597-1_27"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Rama, R., Raman, V., Vijayakumar, S.: lApproximate Block Sorting. International Journal of Foundation of Computer Science, 337\u2013356 (2006)","DOI":"10.1142\/S0129054106003863"},{"issue":"1","key":"28_CR11","first-page":"126","volume":"14","author":"M Mahajan","year":"2007","unstructured":"Mahajan, M., Rama, R., Vijayakumar, S.: Block sorting: a characterization and some heuristics. Nordic Journal of Computing 14(1), 126\u2013150 (2007)","journal-title":"Nordic Journal of Computing"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Rama, R., Vijayakumar, S.: Towards constructing optimal block move sequences. In: Chwa, K.-Y., Munro, J.I. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 33\u201342. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27798-9_6"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T16:21:54Z","timestamp":1674231714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}