{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T02:07:19Z","timestamp":1774922839172,"version":"3.50.1"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,9,14]],"date-time":"2016-09-14T00:00:00Z","timestamp":1473811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["VO 889\/2 and WE 2842\/1"],"award-info":[{"award-number":["VO 889\/2 and WE 2842\/1"]}]},{"name":"EU within the 6th Framework Programme","award":["001907 (DELIS)"],"award-info":[{"award-number":["001907 (DELIS)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"<jats:p>2-Opt is a simple local search heuristic for the traveling salesperson problem that performs very well in experiments with respect to both running time and solution quality. In contrast to this, there are instances on which 2-Opt may need an exponential number of steps to reach a local optimum. To understand why 2-Opt usually finds local optima quickly in experiments, we study its expected running time in the model of smoothed analysis, which can be considered as a less-pessimistic variant of worst-case analysis in which the adversarial input is subject to a small amount of random noise.<\/jats:p>\n          <jats:p>\n            In our probabilistic input model, an adversary chooses an arbitrary graph\n            <jats:italic>G<\/jats:italic>\n            and a probability density function for each edge according to which its length is chosen. We prove that in this model the expected number of local improvements is\n            <jats:italic>O<\/jats:italic>\n            (mn\u03d5 \u010b 16\n            <jats:sup>\n              \u221aln\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            )=\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              1+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n\u03d5<\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>m<\/jats:italic>\n            denote the number of vertices and edges of\n            <jats:italic>G<\/jats:italic>\n            , respectively, and \u03d5 denotes an upper bound on the density functions.\n          <\/jats:p>","DOI":"10.1145\/2972953","type":"journal-article","created":{"date-parts":[[2016,9,14]],"date-time":"2016-09-14T14:38:24Z","timestamp":1473863904000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Smoothed Analysis of the 2-Opt Algorithm for the General TSP"],"prefix":"10.1145","volume":"13","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn, Germany"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2016,9,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251244"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"e_1_2_1_3_1","volume-title":"McGeoch","author":"Johnson David S.","year":"1997"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587089"},{"key":"e_1_2_1_5_1","unstructured":"George S. Lueker. 1975. Unpublished Manuscript. Princeton University.  George S. Lueker. 1975. Unpublished Manuscript. Princeton University."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC). Springer","author":"Manthey Bodo","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2972953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2972953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:16Z","timestamp":1750218616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2972953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,14]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2972953"],"URL":"https:\/\/doi.org\/10.1145\/2972953","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,14]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}