{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T08:28:41Z","timestamp":1772785721085,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T00:00:00Z","timestamp":1726185600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T00:00:00Z","timestamp":1726185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12371317"],"award-info":[{"award-number":["12371317"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s10898-024-01428-7","type":"journal-article","created":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T03:45:17Z","timestamp":1726199117000},"page":"983-1006","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved approximation algorithms for the k-path partition problem"],"prefix":"10.1007","volume":"90","author":[{"given":"Shiming","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6127-1264","authenticated-orcid":false,"given":"Wei","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Zhaohui","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,13]]},"reference":[{"issue":"6","key":"1428_CR1","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1080\/00207549108930121","volume":"29","author":"RG Askin","year":"1991","unstructured":"Askin, R.G., Cresswell, S.H., Goldberg, J.B., Vakharia, A.J.: A hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing. Int. J. Prod. Res. 29(6), 1081\u20131100 (1991)","journal-title":"Int. J. Prod. Res."},{"key":"1428_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1,2)-TSP. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 641\u2013648 (2005)","DOI":"10.1145\/1109557.1109627"},{"key":"1428_CR3","doi-asserted-by":"crossref","unstructured":"Blaser, M.: A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In: Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 61\u201371, Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_6"},{"key":"1428_CR4","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen Z., Kennedy C., Lin, G., Xu, Y., Zhang, A.: Approximation algorithms for the directed path partition problems. In: Proceedings of the International Workshop on Frontiers of Algorithmics. IJTCS-FAW 2021. Lecture Notes in Computer Science, 12874, pp. 23\u201336, Springer (2022)","DOI":"10.1007\/978-3-030-97099-4_2"},{"key":"1428_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105150","volume":"297","author":"Y Chen","year":"2024","unstructured":"Chen, Y., Chen, Z., Kennedy, C., Lin, G., Xu, Y., Zhang, A.: Approximating the directed path partition problems. Inf. Comput. 297, 105150 (2024)","journal-title":"Inf. Comput."},{"key":"1428_CR6","doi-asserted-by":"publisher","first-page":"3595","DOI":"10.1007\/s10878-022-00915-5","volume":"44","author":"Y Chen","year":"2022","unstructured":"Chen, Y., Goebel, R., Lin, G., Liu, L., Su, B., Tong, W., Xu, Y., Zhang, A.: A local search 4\/3-approximation algorithm for the minimum 3-path partition problem. J. Comb. Optim. 44, 3595\u20133610 (2022)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"1428_CR7","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/s10878-018-00372-z","volume":"38","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Goebel, R., Lin, G., Su, B., Xu, Y., Zhang, A.: An improved approximation algorithm for the minimum 3-path partition problem. J. Comb. Optim. 38(1), 150\u2013164 (2019)","journal-title":"J. Comb. Optim."},{"key":"1428_CR8","unstructured":"Chen, Y., Goebel, R., Su, B., Tong, W., Xu, Y., Zhang, A.: A 21\/16-approximation for the minimum 3-path partition problem. In: Proceedings of the 30th International Symposium on Algorithms and Computation, Article No. 46, pp. 46:1\u201346:20 (2019)"},{"key":"1428_CR9","doi-asserted-by":"crossref","unstructured":"Dudycz S., Marcinkowski T., Paluch K., Rybicki B.: A 4\/5-approximation algorithm for the maximum traveling salesman problem. In: Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, pp. 173\u2013185, Springer (2017)","DOI":"10.1007\/978-3-319-59250-3_15"},{"key":"1428_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"issue":"3","key":"1428_CR11","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10107-004-0505-z","volume":"100","author":"AV Goldberg","year":"2004","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100(3), 537\u2013568 (2004)","journal-title":"Math. Program."},{"key":"1428_CR12","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D Karger","year":"1997","unstructured":"Karger, D., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica 18, 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"1428_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"1428_CR14","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D., Hell, P.: On the completeness of a generalized matching problem. In: Proceedings of the tenth Annual ACM Symposium on Theory of Computing, pp. 240\u2013245 (1978)","DOI":"10.1145\/800133.804353"},{"key":"1428_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.endm.2018.05.009","volume":"67","author":"N Korpelainen","year":"2018","unstructured":"Korpelainen, N.: A boundary class for the k-path partition problem. Electron. Notes Discrete Math 67, 49\u201356 (2018)","journal-title":"Electron. Notes Discrete Math"},{"key":"1428_CR16","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ejor.2018.06.002","volume":"272","author":"AN Letchford","year":"2019","unstructured":"Letchford, A.N., Salazar-Gonzalez, J.J.: The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time. Eur. J. Oper. Res. 272, 24\u201331 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"1428_CR17","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s11590-023-01989-8","volume":"18","author":"S Li","year":"2024","unstructured":"Li, S., Yu, W., Liu, Z.: A local search algorithm for the $$k$$-path partition problem. Optim. Lett. 18, 279\u2013290 (2024)","journal-title":"Optim. Lett."},{"issue":"5","key":"1428_CR18","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2006.12.004","volume":"35","author":"J Monnot","year":"2007","unstructured":"Monnot, J., Toulouse, S.: The path partition problem and related problems in bipartite graphs. Oper. Res. Lett. 35(5), 677\u2013684 (2007)","journal-title":"Oper. Res. Lett."},{"key":"1428_CR19","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00224-017-9818-1","volume":"62","author":"K Paluch","year":"2018","unstructured":"Paluch, K.: Maximum ATSP with weights zero and one via half-edges. Theory Comput. Syst. 62, 319\u2013336 (2018)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"1428_CR20","doi-asserted-by":"publisher","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 distance one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"1428_CR21","first-page":"89","volume":"147","author":"G Steiner","year":"2000","unstructured":"Steiner, G.: On the $$k$$-th path partition problem in cographs. Congr. Numer. 147, 89\u201396 (2000)","journal-title":"Congr. Numer."},{"issue":"3","key":"1428_CR22","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/S0304-3975(02)00577-7","volume":"290","author":"G Steiner","year":"2003","unstructured":"Steiner, G.: On the $$k$$-path partition of graphs. Theoret. Comput. Sci. 290(3), 2147\u20132155 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"1428_CR23","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(97)00012-7","volume":"78","author":"J Yan","year":"1997","unstructured":"Yan, J., Chang, G., Hedetiemi, S.M., Hedetniemi, S.T.: $$k$$-path partitions in trees. Discret. Appl. Math. 78(1), 227\u2013233 (1997)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1428_CR24","doi-asserted-by":"publisher","first-page":"0","DOI":"10.3390\/e22010073","volume":"22","author":"W Zhang","year":"2020","unstructured":"Zhang, W., Wang, S., Han, W., Yu, H., Zhu, Z.L.: An image encryption algorithm based on random Hamiltonian path. Entropy 22(1), 0\u201373 (2020)","journal-title":"Entropy"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01428-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01428-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01428-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T14:03:21Z","timestamp":1730297001000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01428-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,13]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1428"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01428-7","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,13]]},"assertion":[{"value":"21 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}