{"entities":{"Q1813831":{"pageid":1824573,"ns":120,"title":"Item:Q1813831","lastrevid":46208434,"modified":"2025-12-24T07:53:04Z","type":"item","id":"Q1813831","labels":{"en":{"language":"en","value":"On patching algorithms for random asymmetric travelling salesman problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5231"}},"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":"Q1813831$8649305A-5ACD-4A18-8DC1-A0D7DE79A1CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5eeabfe8cde25905df0dfe2f625fe3e68b04cb74","datavalue":{"value":{"text":"On patching algorithms for random asymmetric travelling salesman problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1813831$1DDF181C-31F9-4202-BDC1-ACD25977C994","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4eb36164b3a5b41cf77f65185fabfa88e6d9bc5c","datavalue":{"value":"0742.90064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$ED5F59A8-01CA-4A07-8BF3-9AE8F5D233D3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"263a7145d2b85c03ad71f8aedfc554dd35d4be7b","datavalue":{"value":"10.1007/BF01585751","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$66F998DC-77B2-40BD-97F5-C5E74130CD96","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":"Q1813831$25B4D4ED-84F5-4DEB-952A-05F8D20077F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1813831$CFE94CD8-77A0-4ECF-8EB5-D59312190C28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9d22b66e44f48a0803502a7378ee338e0e2dc14","datavalue":{"value":"Let the arc-lengths \\(\\ell_{ij}\\) of a complete digraph of order \\(n\\) be independent uniform \\([0,1]\\) random variables. The authors consider the patching algorithm of \\textit{R. M. Karp} [SIAM J. Comput. 8, 561-573 (1979; Zbl 0427.90064)] and \\textit{R. M. Karp} and \\textit{J. M. Steele} [in: The travelling salesman problem, a guided tour of combinatorial optimization, 181-205 (1985; Zbl 0582.90100)] for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. These ideas are also extended to the \\(k\\)-person travelling salesman problem [see \\textit{G. Frederickson, M. Hecht} and \\textit{C. Kim}, SIAM J. Comput. 7, 178-193 (1978)] and the problem of finding the minimum length closed walk through the vertex set of the digraph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$58CDEED9-39DE-49AD-8787-AD95968C9658","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$FB23B527-0935-412E-9C17-72605D9FA1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$A534A492-B7D4-4CAF-80E6-31D71764A9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$4768C5E3-BEF7-4F43-AF61-C46C9030F3CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$A7FECB28-F29A-49B4-902D-E630B956794E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"74436bdce0632cef6cfd71f4c8f801180f8c242b","datavalue":{"value":"5231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$F814B751-9604-4259-AFAA-5F20DDC0C793","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff2ed59240f81cb0c06949a5dce2e4150bfc8f6a","datavalue":{"value":"complete digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$75689AC6-AECE-4C58-8C85-4FA84D8C15E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3807f37108a0f5b0b5bf4318fd6327c8247e6641","datavalue":{"value":"patching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$90C8BFA8-07F4-4E85-B800-B432AB4EDD8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$99B052B0-55F4-4699-B659-77493D401B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54699d38792349fd5ce4a7717c7aa764749b269c","datavalue":{"value":"\\(k\\)-person travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$5A7E7559-52C3-4E8C-A34B-2D9C10E17BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0487c43d17ba72db5b47c60b635961f96833be5c","datavalue":{"value":"minimum length closed walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813831$1BD62952-F9F0-4DCF-9D6A-546483F3E337","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ac6079b2082bbed271309fb2d51b5b4c5dd28d8","datavalue":{"value":{"entity-type":"item","numeric-id":247119,"id":"Q247119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$6F3D2900-4CBF-48DA-A791-D135B28E501F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$AAA1AC5D-BA5E-463E-A89E-370478F23B10","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":"Q1813831$4FD619AD-0EE2-4CF7-A86C-2ACBD0882745","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6647def04be7860ae9c397e02ad3ab4c1cc95ff2","datavalue":{"value":"Q56324130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813831$8116A013-7FEB-4A90-A2F1-B5554B9F0613","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$069592AB-2C82-4C09-9591-A1778FF9B19A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d47fa6214894c3bf2d0d9847f974baa6104efa3c","datavalue":{"value":{"entity-type":"item","numeric-id":3686500,"id":"Q3686500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$EBBECA90-5321-45B5-83BD-46D541198E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"924c7ed8697c312a9a8d8ead9fe1d5a68c47916b","datavalue":{"value":{"entity-type":"item","numeric-id":1086251,"id":"Q1086251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$B0CFCD71-DECB-439C-8599-C4596E23E513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$5DBBD884-960C-4FD3-BEA4-CEE4932AB8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e201bc51243fe20d8c466e86b983d9f7797bbdce","datavalue":{"value":{"entity-type":"item","numeric-id":3863432,"id":"Q3863432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$E8D89F2B-ABBF-40CB-AA48-1E07D13E209D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813831$E24D7135-46FF-4D11-B80B-6ABFCAE1E79E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3305cc3bf1ff46d97e614e76a5e430ffa76c5aec","datavalue":{"value":{"entity-type":"item","numeric-id":3730367,"id":"Q3730367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c9db23332a68dfbb138a4910afab94af811f063","datavalue":{"value":{"amount":"+0.8170161247253418","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":"Q1813831$26B15894-9F41-43ED-9B6E-BDABE9373CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24673d17188347e4317844b7ac1a683c2077dd21","datavalue":{"value":{"entity-type":"item","numeric-id":1602706,"id":"Q1602706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"654e75458299ca2148f7227e2074fedee1cecb84","datavalue":{"value":{"amount":"+0.7789695262908936","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":"Q1813831$D7448C6B-A5D5-4B71-98B0-51CD1354E146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"525a18f3be69962437874607a2a42654fd8d9e2f","datavalue":{"value":{"entity-type":"item","numeric-id":3801370,"id":"Q3801370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"013114962883bf9fca6b6ba5b980cbe780238c51","datavalue":{"value":{"amount":"+0.7705975770950317","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":"Q1813831$9C89D477-F7AA-43A0-8A4F-9C26B5D740D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35d30f9f5844e3d460bfc7eca202718f9f02e47","datavalue":{"value":{"entity-type":"item","numeric-id":5704203,"id":"Q5704203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61a3f346cd122011582d4d21158bee0a67aa5c9a","datavalue":{"value":{"amount":"+0.769049882888794","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":"Q1813831$70775898-DA75-44EC-8FBD-1F812291B72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1578c002fe2475fbbf5fa8353456a71fb69050eb","datavalue":{"value":{"entity-type":"item","numeric-id":3428835,"id":"Q3428835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d16f7e1242511fa5c938f55d9d105baa9af85e7","datavalue":{"value":{"amount":"+0.7690342664718628","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":"Q1813831$693BDEC3-A3E1-4609-9003-1916AB5D7F65","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1813831","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1813831"}}}}}