{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:52:46Z","timestamp":1773820366333,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,12,18]],"date-time":"2015-12-18T00:00:00Z","timestamp":1450396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"crossref","award":["14-11-00109"],"award-info":[{"award-number":["14-11-00109"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s10898-015-0391-3","type":"journal-article","created":{"date-parts":[[2015,12,18]],"date-time":"2015-12-18T00:03:36Z","timestamp":1450397016000},"page":"65-82","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Approximability of the minimum-weight k-size cycle cover problem"],"prefix":"10.1007","volume":"66","author":[{"given":"Michael","family":"Khachay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katherine","family":"Neznakhina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,18]]},"reference":[{"key":"391_CR1","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial-time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"9","key":"391_CR2","doi-asserted-by":"crossref","first-page":"1988","DOI":"10.1016\/j.dam.2008.06.025","volume":"157","author":"A Baburin","year":"2009","unstructured":"Baburin, A., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.T.: Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157(9), 1988\u20131992 (2009)","journal-title":"Discrete Appl. Math."},{"key":"391_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34, 209\u2013219 (2006). doi: 10.1016\/j.omega.2004.10.004","journal-title":"Omega"},{"key":"391_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00453-004-1131-0","volume":"42","author":"M Bl\u00e4ser","year":"2005","unstructured":"Bl\u00e4ser, M., Manthey, B.: Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica 42, 121\u2013139 (2005). doi: 10.1007\/s00453-004-1131-0","journal-title":"Algorithmica"},{"key":"391_CR5","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.jda.2005.07.004","volume":"4","author":"M Bl\u00e4ser","year":"2006","unstructured":"Bl\u00e4ser, M., Manthey, B., Sgall, J.: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4, 623\u2013632 (2006). doi: 10.1016\/j.jda.2005.07.004","journal-title":"J. Discrete Algorithms"},{"key":"391_CR6","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Siebert, B.: Computing cycle covers without short cycles. In: Algorithms ESA 2001, pp. 368\u2013379. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44676-1_31"},{"key":"391_CR7","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.tcs.2006.10.026","volume":"370","author":"LS Chandran","year":"2007","unstructured":"Chandran, L.S., Ram, L.S.: On the relationship between ATSP and the cycle cover problem. Theor. Comput. Sci. 370, 218\u2013228 (2007). doi: 10.1016\/j.tcs.2006.10.026","journal-title":"Theor. Comput. Sci."},{"key":"391_CR8","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)"},{"key":"391_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, New York (2001)","edition":"2"},{"issue":"1","key":"391_CR10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manag. Sci."},{"key":"391_CR11","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/02331939108843650","volume":"20","author":"J Kort De","year":"1991","unstructured":"De Kort, J.: Lower bounds for symmetric k-peripatetic salesman problems. Optimization 20, 113\u2013122 (1991)","journal-title":"Optimization"},{"key":"391_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"RA Finkel","year":"1974","unstructured":"Finkel, R.A., Bentley, J.L.: Quad trees: a data structure for retrieval on composite keys. Acta Inf. 4, 1\u20139 (1974). doi: 10.1007\/BF00288933","journal-title":"Acta Inf."},{"key":"391_CR13","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. W. H. Freeman & Co., New York (1979)"},{"key":"391_CR14","doi-asserted-by":"crossref","first-page":"S57","DOI":"10.1134\/S0081543808060072","volume":"263","author":"E Gimadi","year":"2008","unstructured":"Gimadi, E.: Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in euclidean space. Proc. Steklov Inst. Math. 263, S57\u2013S67 (2008)","journal-title":"Proc. Steklov Inst. Math."},{"key":"391_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-77778-8","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research\/Computer Science Interfaces Series","author":"B Golden","year":"2008","unstructured":"Golden, B., Raghavan, S., Wasil, E.A.: The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research\/Computer Science Interfaces Series, vol. 43. Springer, Berlin (2008)"},{"key":"391_CR16","first-page":"241","volume":"123","author":"H Jung","year":"1901","unstructured":"Jung, H.: \u00dcber die kleinste kugel, die eine r\u00e4umliche figur einschliesst. J. Reine Angew. Math. 123, 241\u2013257 (1901)","journal-title":"J. Reine Angew. Math."},{"key":"391_CR17","doi-asserted-by":"crossref","unstructured":"Krarup, J.: The peripatetic salesman and some related unsolved problems. In: Roy, B. (ed.) Combinatorial Programming: Methods and Applications, pp. 173\u2013178. Springer, Netherlands (1975)","DOI":"10.1007\/978-94-011-7557-9_8"},{"key":"391_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.4236\/iim.2012.43010","volume":"4","author":"S Kumar","year":"2012","unstructured":"Kumar, S., Panneerselvam, R.: A survey on the vehicle routing problem and its variants. Intell. Inf. Manag. 4, 66\u201374 (2012). doi: 10.4236\/iim.2012.43010","journal-title":"Intell. Inf. Manag."},{"key":"391_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/060676003","volume":"38","author":"B Manthey","year":"2008","unstructured":"Manthey, B.: On approximating restricted cycle covers. SIAM J. Comput. 38, 181\u2013206 (2008). doi: 10.1137\/060676003","journal-title":"SIAM J. Comput."},{"key":"391_CR20","doi-asserted-by":"publisher","first-page":"1470","DOI":"10.1016\/j.dam.2008.10.005","volume":"157","author":"B Manthey","year":"2009","unstructured":"Manthey, B.: Minimum-weight cycle covers and their approximability. Discrete Appl. Math. 157, 1470\u20131480 (2009). doi: 10.1016\/j.dam.2008.10.005","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"391_CR21","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.: Euclidean TSP is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"391_CR22","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzales, T.: P-complete approximation problems. J. ACM 23, 555\u2013565 (1976)","journal-title":"J. ACM"},{"key":"391_CR23","unstructured":"Szwarcfiter, J., Wilson, L.: The cycle cover problem. Tech. Rep. 131, University of Newcastle upon Tyne (1979)"},{"key":"391_CR24","volume-title":"The Vehicle Routing Problem","year":"2001","unstructured":"Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia (2001)"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-015-0391-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-015-0391-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-015-0391-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T13:42:08Z","timestamp":1567431728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-015-0391-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,18]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["391"],"URL":"https:\/\/doi.org\/10.1007\/s10898-015-0391-3","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,18]]}}}