{"entities":{"Q1122505":{"pageid":1133254,"ns":120,"title":"Item:Q1122505","lastrevid":66808017,"modified":"2026-04-12T13:00:56Z","type":"item","id":"Q1122505","labels":{"en":{"language":"en","value":"A probabilistic analysis of the switching algorithm for the Euclidean TSP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4106633"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$CF68B610-4028-4E20-9B6A-73C209B0DEE7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e4d7204f665d29331903e0b59e37a8eee155452f","datavalue":{"value":{"text":"A probabilistic analysis of the switching algorithm for the Euclidean TSP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122505$8539E6EF-3BD9-448E-912F-540712310ADF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"326a1757320c4ef9225ae37783ea28dbd5505bae","datavalue":{"value":"0675.90086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122505$D0AFDDEF-C69C-4B0D-A480-784D62369571","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c15480fb36dde00745a21a8ba28f17c9c647301c","datavalue":{"value":"10.1007/BF01587089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122505$DEE0D648-631D-4911-8739-F82E44E7F5DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03794ad79d6c849c6904d9a0e8304a678b4ad199","datavalue":{"value":{"entity-type":"item","numeric-id":170461,"id":"Q170461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$50D0F14E-B02C-441A-8236-6EC5B1E6125C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$E74C3A85-F9FB-40FA-8D67-381EA79CA982","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1122505$063F1EE0-73CF-4AE2-8D03-4E4C9575BA32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b0ea112ff5615f0da185f26d7d838fbd5cf6cd23","datavalue":{"value":"The 2-switching Algorithm for the Euclidean Traveling Salesman problem is studied. A probabilistic analysis is developed. It gives an evaluation of a simulated annealing version of the Lin-Kernigham algorithm. A bound of the number of points (n) and the minimum distance (d*) between a tour \\(\\sigma\\) and that generated by switching points \\(\\tau_ i\\) and \\(\\sigma_ j\\) is defined. For small d*'s the necessary computation can be too time-consuming. In order to prove a lemma, \\(A_{\\epsilon}(i,j,k)\\) is fixed as the set of points x such that the absolute value of a function F(i,j,k,x) is bounded by an arbitrary \\(\\epsilon >0\\). The lemma establishes that this set is bounded and the bound is calculated. The behavior of a strategy for fixing paths is analyzed in a ``claim''. This claim is a corrollary to the lemma. It is proved and two figures illustrate the involved ideas.    The probability that the algorithm stops after no more than \\(O(n^{18})\\) steps is 1-(d(x,i)-d(x,j)). The possibility of developing a k-switching algorithm is sketched.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122505$13EAC185-AA60-4253-BAB3-E3FA5EA1BA23","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122505$3E1BE5A4-BBAF-49EA-8C24-3F041F95EE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122505$71EC28A9-EEB9-4389-8FCF-8E37769AB7B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6204010cfa9390e38d6202040b14e30ffc568ecf","datavalue":{"value":"4106633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122505$C9C184DA-E483-47CF-9767-268F83BEC5D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3de845eaf9fce2d5114237bea83f798cbe4027fa","datavalue":{"value":"Euclidean Traveling Salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122505$7E2467C2-67B4-49CF-9795-280C30DD6B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122505$36C1D048-75DD-4D8D-8B21-C1D9CD7E83FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"605eaf52a7d40b4ca440dd997a658542e33d5665","datavalue":{"value":"simulated annealing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122505$FD344BCE-6B96-46E3-8A8C-43C8B97BE390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc7a45e6147e9e0386f5211a4ccabc9b68438d30","datavalue":{"value":"k-switching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122505$BE60C088-292B-4E4B-A438-E4334593FF37","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e146cd479742131190191fb6e4c868c8b1c80b43","datavalue":{"value":{"entity-type":"item","numeric-id":591644,"id":"Q591644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$B33B3D60-1FA6-484C-A052-98904554E675","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$992F2616-AE4A-4C78-9C45-6203FB42F1AB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d66d3b01efe503acb9598115738bcf0084218c8","datavalue":{"value":{"entity-type":"item","numeric-id":3343803,"id":"Q3343803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$0D1396DA-AE9A-47F7-ACEC-240DA8969AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"295a70c178855625d44b3d929ce0d3758a1bb37f","datavalue":{"value":{"entity-type":"item","numeric-id":4144785,"id":"Q4144785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$95ADF728-7F26-4A5A-A4C4-3E265953AB6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0930d57b126d4670b8351b41154baa4cb1f96e2","datavalue":{"value":{"entity-type":"item","numeric-id":5671788,"id":"Q5671788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$025F3B62-E9AB-462E-B187-3307CF73B28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2d7941d0b26099a80a70765368bbd5212826ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3677509,"id":"Q3677509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$D5FB3A55-10A2-4D57-96FA-7F2E3D279A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77a843764d9d3b38ca1313ed42e674cf1056362f","datavalue":{"value":{"entity-type":"item","numeric-id":1079126,"id":"Q1079126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$1D751CAA-B7EF-4C59-A3CA-37CEE873CD5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5090218963f7454eb65bbbfc3a5878c945557f","datavalue":{"value":{"entity-type":"item","numeric-id":4162995,"id":"Q4162995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$B087CFC4-DE62-4481-A67E-06F1AAE62B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df23e8c2866cf210e52009ddc87ceaca0598ccc","datavalue":{"value":{"entity-type":"item","numeric-id":594546,"id":"Q594546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122505$901F5B8B-979B-417B-80E4-E1E2D84FC789","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5874570c1df31d6c42f96936b2537e39826cfa2c","datavalue":{"value":{"entity-type":"item","numeric-id":1079126,"id":"Q1079126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"270e99b296f9478591546b9291562b60c4d48efc","datavalue":{"value":{"amount":"+0.7950840592384338","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122505$B73D0CE5-0727-47CB-87A5-7FABCF3CA64E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d71d0322fb5d12b18cbd35264759e66c67b1a0","datavalue":{"value":{"entity-type":"item","numeric-id":2934725,"id":"Q2934725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"417553412ed0b82b77a61a21e5e2beddcab887fa","datavalue":{"value":{"amount":"+0.779022753238678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122505$ACF89C0C-A490-436C-8AA1-6247A52C36D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97146612761237142c692504f981f112fa337a1c","datavalue":{"value":{"entity-type":"item","numeric-id":2904559,"id":"Q2904559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"322f306993f2338e031af233f31c6bac2a2b65bf","datavalue":{"value":{"amount":"+0.7788037657737732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122505$46BBB683-E0C0-4BBA-8B74-100E3AFCBE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06c333ec1c0069dc1aab83eb54b463cbbf2b2d58","datavalue":{"value":{"entity-type":"item","numeric-id":3707785,"id":"Q3707785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"892e684b1c7e8dbbf5259fcbed8f6940a2517c77","datavalue":{"value":{"amount":"+0.77720707654953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122505$71AA11F2-F6F0-41DA-AA75-02A058B40F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f735ba9b39faec3b9c8b05006427ce465788e439","datavalue":{"value":{"entity-type":"item","numeric-id":3337225,"id":"Q3337225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1449cc63b5160178268fc333a58f3eb06dc9a07","datavalue":{"value":{"amount":"+0.7646133303642273","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122505$15452373-2A2B-4450-81C4-9FCFF3F77B7C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A probabilistic analysis of the switching algorithm for the Euclidean TSP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_probabilistic_analysis_of_the_switching_algorithm_for_the_Euclidean_TSP"}}}}}