{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:10:53Z","timestamp":1784110253357,"version":"3.55.0"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11671135"],"award-info":[{"award-number":["11671135"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11871213"],"award-info":[{"award-number":["11871213"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Shanghai","award":["19ZR1411800"],"award-info":[{"award-number":["19ZR1411800"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p> Given an undirected complete graph [Formula: see text] on [Formula: see text] vertices with a non-negative weight function on [Formula: see text], the maximum-weight [Formula: see text]-cycle ([Formula: see text]-path) packing problem aims to compute a set of [Formula: see text] vertex-disjoint cycles (paths) in [Formula: see text] containing [Formula: see text] vertices so that the total weight of the edges in these [Formula: see text] cycles (paths) is maximized. For the maximum-weight [Formula: see text]-cycle packing problem, we develop an algorithm achieving an approximation ratio of [Formula: see text], where [Formula: see text] is the approximation ratio for the maximum traveling salesman problem. For the case [Formula: see text], we design a better [Formula: see text]-approximation algorithm. When the weights of edges obey the triangle inequality, we propose a [Formula: see text]-approximation algorithm and a [Formula: see text]-approximation algorithm for the maximum-weight [Formula: see text]-cycle packing problem with [Formula: see text] and [Formula: see text], respectively. For the maximum-weight [Formula: see text]-path packing problem with [Formula: see text] (or [Formula: see text]) with the triangle inequality, we devise an algorithm with approximation ratio [Formula: see text] and give a tight example. <\/jats:p>","DOI":"10.1142\/s0217595923400031","type":"journal-article","created":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T03:25:45Z","timestamp":1672975545000},"source":"Crossref","is-referenced-by-count":9,"title":["Approximation Algorithms for the Maximum-Weight Cycle\/Path Packing Problems"],"prefix":"10.1142","volume":"40","author":[{"given":"Shiming","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Yu","sequence":"additional","affiliation":[{"name":"School of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2023,5,27]]},"reference":[{"key":"S0217595923400031BIB001","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1287\/moor.23.3.640","volume":"23","author":"Arkin E","year":"1998","journal-title":"Mathematics of Operations Research"},{"key":"S0217595923400031BIB002","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s00453-004-1087-0","volume":"39","author":"Arkin E","year":"2004","journal-title":"Algorithmica"},{"key":"S0217595923400031BIB003","first-page":"519","volume-title":"Proc. 28th Int. Symp. Theoretical Aspects of Computer Science (STACS 2011)","author":"Babenko M","year":"2011"},{"key":"S0217595923400031BIB004","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.dam.2017.11.031","volume":"239","author":"Bar-Noy A","year":"2018","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400031BIB005","first-page":"214","volume-title":"Proc. 7th Scandinavian Workshop on Algorithm Theory","author":"Berman P","year":"2000"},{"key":"S0217595923400031BIB006","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1142\/S1793830909000373","volume":"1","author":"Biro P","year":"2009","journal-title":"Discrete Mathematics, Algorithms and Applications"},{"key":"S0217595923400031BIB007","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/s10878-020-00660-7","volume":"41","author":"Chen Y","year":"2021","journal-title":"Journal of Combinatorial Optimization"},{"key":"S0217595923400031BIB008","doi-asserted-by":"crossref","first-page":"1640","DOI":"10.1016\/j.dam.2008.11.009","volume":"157","author":"Chen Z","year":"2009","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400031BIB009","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1016\/j.dam.2010.01.011","volume":"158","author":"Chen Z","year":"2010","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400031BIB010","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-319-59250-3_15","volume-title":"Proc. 19th Int. Conf. Integer Programming and Combinatorial Optimization (IPCO 2017)","author":"Dudycz S","year":"2017"},{"key":"S0217595923400031BIB011","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0020-0190(97)00097-5","volume":"63","author":"Hassin R","year":"1997","journal-title":"Information Processing Letters"},{"key":"S0217595923400031BIB012","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/j.dam.2005.11.003","volume":"154","author":"Hassin R","year":"2006","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400031BIB013","doi-asserted-by":"crossref","first-page":"2620","DOI":"10.1016\/j.dam.2006.05.005","volume":"154","author":"Hassin R","year":"2006","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400031BIB014","first-page":"240","volume-title":"Proc. 10th Annual ACM Symp. Theory of Computing","author":"Kirkpatrick D","year":"1978"},{"key":"S0217595923400031BIB015","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-56039-6","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte B","year":"2018","edition":"6"},{"issue":"47","key":"S0217595923400031BIB016","doi-asserted-by":"crossref","first-page":"5000","DOI":"10.1016\/j.tcs.2009.07.051","volume":"410","author":"Kowalik L","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"S0217595923400031BIB017","doi-asserted-by":"crossref","first-page":"3165","DOI":"10.1007\/s00453-020-00719-1","volume":"82","author":"Kutiel G","year":"2020","journal-title":"Algorithmica"},{"key":"S0217595923400031BIB018","volume-title":"Combinatorial Optimization: Networks and Matroids.","author":"Lawler EL","year":"1976"},{"key":"S0217595923400031BIB019","first-page":"53:1","volume-title":"Proc. 28th Int. Symp. Theoretical Aspects of Computer Science (STACS 2021)","author":"Neuwohner M","year":"2021"},{"key":"S0217595923400031BIB020","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/978-3-031-06901-7_31","volume-title":"Proc. 23rd Int. Conf. Integer Programming and Combinatorial Optimization (IPCO 2022)","volume":"13265","author":"Neuwohner M","year":"2022"},{"issue":"2","key":"S0217595923400031BIB021","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1587\/transinf.E93.D.241","volume":"93","author":"Tanahashi R","year":"2010","journal-title":"IEICE Transactions on Information and Systems"},{"key":"S0217595923400031BIB022","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1287\/moor.1090.0418","volume":"34","author":"Nagarajan V","year":"2009","journal-title":"Mathematics of Operations Research"},{"key":"S0217595923400031BIB023","doi-asserted-by":"crossref","first-page":"2142","DOI":"10.1016\/j.dam.2013.03.001","volume":"161","author":"Van Zuylen A","year":"2013","journal-title":"Discrete Applied Mathematics"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595923400031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T07:04:14Z","timestamp":1693465454000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595923400031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,27]]},"references-count":23,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1142\/S0217595923400031"],"URL":"https:\/\/doi.org\/10.1142\/s0217595923400031","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,27]]},"article-number":"2340003"}}