{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T02:17:40Z","timestamp":1768616260435,"version":"3.49.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319592497","type":"print"},{"value":"9783319592503","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_15","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"173-185","source":"Crossref","is-referenced-by-count":10,"title":["A 4\/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Szymon","family":"Dudycz","sequence":"first","affiliation":[]},{"given":"Jan","family":"Marcinkowski","sequence":"additional","affiliation":[]},{"given":"Katarzyna","family":"Paluch","sequence":"additional","affiliation":[]},{"given":"Bartosz","family":"Rybicki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"15_CR1","unstructured":"Arkin, E.M., Chiang, Y., Mitchell, J.S.B., Skiena, S., Yang, T.: On the maximum scatter TSP (extended abstract). In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 211\u2013220 (1997)"},{"issue":"5","key":"15_CR2","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/876638.876640","volume":"50","author":"AI Barvinok","year":"2003","unstructured":"Barvinok, A.I., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641\u2013664 (2003)","journal-title":"J. ACM"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-69346-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Barvinok","year":"1998","unstructured":"Barvinok, A., Johnson, D.S., Woeginger, G.J., Woodroofe, R.: The maximum traveling salesman problem under polyhedral norms. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 195\u2013201. Springer, Heidelberg (1998). doi:\n10.1007\/3-540-69346-7_15"},{"key":"15_CR4","unstructured":"Bhatia, R.: Private communication"},{"issue":"6","key":"15_CR5","doi-asserted-by":"crossref","first-page":"2133","DOI":"10.1137\/S0097539795295468","volume":"28","author":"P Chalasani","year":"1999","unstructured":"Chalasani, P., Motwani, R.: Approximating capacitated routing and delivery problems. SIAM J. Comput. 28(6), 2133\u20132149 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"15_CR6","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.ipl.2005.03.011","volume":"95","author":"ZZ Chen","year":"2005","unstructured":"Chen, Z.Z., Okamoto, Y., Wang, L.: Improved deterministic approximation algorithms for max TSP. Inf. Process. Lett. 95(2), 333\u2013342 (2005)","journal-title":"Inf. Process. Lett."},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-31770-5_17","volume-title":"Combinatorial Optimization and Applications","author":"Z-Z Chen","year":"2012","unstructured":"Chen, Z.-Z., Wang, L.: An improved approximation algorithm for the bandpass-2 problem. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 188\u2013199. Springer, Heidelberg (2012). doi:\n10.1007\/978-3-642-31770-5_17"},{"issue":"4","key":"15_CR8","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00453-004-1124-z","volume":"41","author":"YJ Chiang","year":"2005","unstructured":"Chiang, Y.J.: New approximation results for the maximum scatter tsp. Algorithmica 41(4), 309\u2013341 (2005)","journal-title":"Algorithmica"},{"key":"15_CR9","unstructured":"Dudycz, S., Marcinkowski, J., Paluch, K.E., Rybicki, B.: A 4\/5 - approximation algorithm for the maximum traveling salesman problem. CoRR abs\/1512.09236 (2015). \nhttp:\/\/arxiv.org\/abs\/1512.09236"},{"issue":"4","key":"15_CR10","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1287\/opre.27.4.799","volume":"27","author":"ML Fisher","year":"1979","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for finding a maximum weight hamiltonian circuit. Oper. Res. 27(4), 799\u2013809 (1979)","journal-title":"Oper. Res."},{"issue":"2","key":"15_CR11","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.disopt.2008.12.003","volume":"6","author":"R Hassin","year":"2009","unstructured":"Hassin, R., Levin, A., Rubinstein, S.: Approximation algorithms for maximum latency and partial cycle cover. Discrete Optim. 6(2), 197\u2013205 (2009)","journal-title":"Discrete Optim."},{"issue":"3","key":"15_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0020-0190(98)00102-1","volume":"67","author":"R Hassin","year":"1998","unstructured":"Hassin, R., Rubinstein, S.: An approximation algorithm for the maximum traveling salesman problem. Inf. Process. Lett. 67(3), 125\u2013130 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"15_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(00)00097-1","volume":"75","author":"R Hassin","year":"2000","unstructured":"Hassin, R., Rubinstein, S.: Better approximations for max TSP. Inf. Process. Lett. 75(4), 181\u2013186 (2000)","journal-title":"Inf. Process. Lett."},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-540-30140-0_37","volume-title":"Algorithms \u2013 ESA 2004","author":"R Hassin","year":"2004","unstructured":"Hassin, R., Rubinstein, S.: An approximation algorithm for maximum triangle packing. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 403\u2013413. Springer, Heidelberg (2004). doi:\n10.1007\/978-3-540-30140-0_37"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. In: 44th Symposium on Foundations of Computer Science (FOCS 2003) (2003)","DOI":"10.1109\/SFCS.2003.1238181"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R., Park, J.K., Stein, C.: Long tours and short superstrings. In: 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1994)","DOI":"10.1109\/SFCS.1994.365696"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-540-73951-7_51","volume-title":"Algorithms and Data Structures","author":"\u0141 Kowalik","year":"2007","unstructured":"Kowalik, \u0141., Mucha, M.: 35\/44-approximation for asymmetric maximum TSP with triangle inequality. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 589\u2013600. Springer, Heidelberg (2007). doi:\n10.1007\/978-3-540-73951-7_51"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-85363-3_11","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"\u0141 Kowalik","year":"2008","unstructured":"Kowalik, \u0141., Mucha, M.: Deterministic 7\/8-approximation for the metric maximum TSP. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX\/RANDOM -2008. LNCS, vol. 5171, pp. 132\u2013145. Springer, Heidelberg (2008). doi:\n10.1007\/978-3-540-85363-3_11"},{"issue":"3","key":"15_CR19","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.ejor.2003.09.007","volume":"161","author":"J Monnot","year":"2005","unstructured":"Monnot, J.: Approximation algorithms for the maximum hamiltonian path problem with specified endpoint(s). Eur. J. Oper. Res. 161(3), 721\u2013735 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"15_CR20","unstructured":"Paluch, K.E.: Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. CoRR (2014)"},{"key":"15_CR21","unstructured":"Paluch, K.E., Elbassioni, K.M., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In: 29th International Symposium on Theoretical Aspects of Computer Science, STACS (2012)"},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-03685-9_23","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K Paluch","year":"2009","unstructured":"Paluch, K., Mucha, M., Ma\u0327dry, A.: A 7\/9 - approximation algorithm for the maximum traveling salesman problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\/RANDOM -2009. LNCS, vol. 5687, pp. 298\u2013311. Springer, Heidelberg (2009). doi:\n10.1007\/978-3-642-03685-9_23"},{"issue":"1","key":"15_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"15_CR24","unstructured":"Schrijver, A.: Nonbipartite matching and covering. In: Combinatorial Optimization, vol. A, pp. 520\u2013561. Springer (2003)"},{"key":"15_CR25","unstructured":"Serdyukov, A.I.: An algorithm with an estimate for the traveling salesman problem of maximum. Upravlyaemye Sistemy 25, 80\u201386 (1984) (in Russian)"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-662-48221-6_14","volume-title":"Algorithms in Bioinformatics","author":"Z Sichen","year":"2015","unstructured":"Sichen, Z., Zhao, L., Liang, Y., Zamani, M., Patro, R., Chowdhury, R., Arkin, E.M., Mitchell, J.S.B., Skiena, S.: Optimizing read reversals for sequence compression. In: Pop, M., Touzet, H. (eds.) WABI 2015. LNCS, vol. 9289, pp. 189\u2013202. Springer, Heidelberg (2015). doi:\n10.1007\/978-3-662-48221-6_14"},{"key":"15_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-319-03780-6_5","volume-title":"Combinatorial Optimization and Applications","author":"W Tong","year":"2013","unstructured":"Tong, W., Goebel, R., Liu, T., Lin, G.: Approximation algorithms for the maximum multiple RNA interaction problem. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 49\u201359. Springer, Cham (2013). doi:\n10.1007\/978-3-319-03780-6_5"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:07:58Z","timestamp":1495530478000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}