{"entities":{"Q643801":{"pageid":645649,"ns":120,"title":"Item:Q643801","lastrevid":51358457,"modified":"2026-01-17T22:12:11Z","type":"item","id":"Q643801","labels":{"en":{"language":"en","value":"On the asymptotic optimality of an algorithm for solving the maximum \\(m\\)-PSP in a multidimensional Euclidean space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5966604"}},"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":"Q643801$E39F031E-74D2-44D5-BDBD-163D9A4080B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d1831755f59888287b17e2c51704e7445d3df05","datavalue":{"value":{"text":"On the asymptotic optimality of an algorithm for solving the maximum \\(m\\)-PSP in a multidimensional Euclidean space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q643801$F3A53D15-AF6B-446F-8312-DC6758063D48","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd74df905a12d4a9542dc71d4d925c0477781b74","datavalue":{"value":"1230.65065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q643801$FFCE71E3-1C35-4AFF-95EE-A4BA286E2134","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97d7eb2ef61eeb95962ea1ea2f9d0befe79c831b","datavalue":{"value":"10.1134/S0081543811020015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q643801$5476019F-29E8-4027-A5AB-C4C53E9A22A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d04198bca28da6696c695b23c84ec1d09f4efb9","datavalue":{"value":{"entity-type":"item","numeric-id":294359,"id":"Q294359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$BDC489E9-6615-4349-9AA3-ACFA0AFECD82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cdb57e2cbeae18b92b24868a6c18c4180ac6cde8","datavalue":{"value":{"entity-type":"item","numeric-id":2457272,"id":"Q2457272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$952BE217-FA6B-41AF-9836-8749D35EDD2A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52ab463cca8ead400441fcc2b4fac1f6fbb55915","datavalue":{"value":{"entity-type":"item","numeric-id":251486,"id":"Q251486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$0672DDD0-4EDF-4385-9337-70F061ACA377","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c140d2afb186d6bcaa772de351445d7226927b0","datavalue":{"value":{"time":"+2011-11-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q643801$BA700AEE-6877-4E51-8BB6-526AA02FF8E5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eaf270402d10d78c8810be9460b9bd94e588f38f","datavalue":{"value":"The authors consider the problem of finding \\(m\\) edge-disjoint salesman tours. The problem is known also as the \\(m\\)-peripatetic salesman problem (\\(m\\)-PSP). The problem can be formulated as follows. A complete \\(n\\)-vertex undirected graph \\(G= (V,E)\\) is given, where \\(V= \\{1,\\dots, n\\}\\) is the set of vertices and \\(E= \\{e= (v,u)\\); \\(v,u\\in V\\), \\(v< u\\}\\) is the set of edges. A nonnegative weight function \\(w: E\\to R_+\\) is defined on \\(E\\). It is required to find \\(m\\) edge-disjoint traveling salesman tours \\(H_1,\\dots, H_m\\subset E\\) such that the total weight of edges in the tours found is maximal. The authors propose an approximation algorithm for solving the \\(m\\)-PSP in a multidimensional Euclidean space and prove an upper bound for the number \\(m\\) of tours for which the algorithm gives an asymptotically optimal solution in polynomial time \\(O(n^3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q643801$831E1947-375D-4F85-AA37-3316F77369B8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ede5e36d99765c94dd5c6a42dd41c767ba4453ac","datavalue":{"value":{"entity-type":"item","numeric-id":300797,"id":"Q300797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$2F115429-EE42-4907-8DF4-110FF577AFB4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q643801$F05BA5B9-F16C-4E90-9629-B5D36F0DCF74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c255b4c62e95aa1b5d9bf81da7207713d23b9629","datavalue":{"value":"5966604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q643801$0F2A1F0E-CDCE-4DB8-AF61-EE1079EA46A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11c8175b9c5feca52c4778e88a7e36c1d67e44d5","datavalue":{"value":"maximum traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q643801$FCDFBFE8-35F6-4466-BD4E-E70DAF1C7B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"007b9cb93174d124ba93c24bf71bc1d38aa75bfb","datavalue":{"value":"edge-disjoint Hamiltonian circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q643801$244157EC-1AA5-49F5-83BA-C5633A217830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10db8fb859c85795509962c81d4d3015099e0f90","datavalue":{"value":"asymptotic optimality","type":"string"},"datatype":"string"},"type":"statement","id":"Q643801$42803206-8A70-41B2-BEC0-5C0A21683836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q643801$F6043673-F802-49F7-8D31-AD2D04C01194","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":"Q643801$49016AB4-C938-4D4F-93A8-58BA8156F9CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dd084ff1d5f2ca643b1c0a1ec191dd3fe5358e6","datavalue":{"value":{"entity-type":"item","numeric-id":1026101,"id":"Q1026101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$A7512273-8F1A-42B0-9458-538F08D3D09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$887F7C68-435E-4341-B186-B7690EC4F6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f8615b9e34afb29cfc2a0cf7ff822cb45b4f513","datavalue":{"value":{"entity-type":"item","numeric-id":1310027,"id":"Q1310027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$93717B74-92AC-4589-9A16-7C2D46D22BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a5ee57399a93d561323b5ef10f5c75c5c904dd9","datavalue":{"value":{"entity-type":"item","numeric-id":5749147,"id":"Q5749147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$FF3ED404-92A9-435D-BCDE-16140E7DD53C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f030d49769421de93ba4d8c53706308a5ef4c44c","datavalue":{"value":{"entity-type":"item","numeric-id":5187226,"id":"Q5187226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$E8322FAC-D8B6-4186-BED3-89A57D48B22D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64bdc83fd07ffe71864d11fda358f7b4c517cd3d","datavalue":{"value":{"entity-type":"item","numeric-id":1612766,"id":"Q1612766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$AFA90A8D-EB40-47C8-A440-29ED016E8A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"217885f69c5700a2364fcdd6e550b0dc2e77138b","datavalue":{"value":{"entity-type":"item","numeric-id":1868811,"id":"Q1868811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q643801$D5660272-993E-4332-98DE-16E6F3C7B5B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7efcd919d4b6162143a4302b479dabce4d432223","datavalue":{"value":"https://doi.org/10.1134/s0081543811020015","type":"string"},"datatype":"url"},"type":"statement","id":"Q643801$4D04DBF1-6B03-41A7-8B21-DB5603594916","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b29007c7d9eac28550165c3cd7561fea1641ad7f","datavalue":{"value":"W2015657372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q643801$34FD7A24-E2B7-4B5D-8900-C7A784CFCB01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c64a6ba78c62b0ab4b24862dc693559dcffc57a6","datavalue":{"value":{"entity-type":"item","numeric-id":735647,"id":"Q735647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8aefebe8b19106d6a6532693621e6e2f28d5114","datavalue":{"value":{"amount":"+0.8533884882926941","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":"Q643801$00244D58-E117-4C54-91A5-24A26E7AC0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a28417afc4e6c2cc6e31eaae952dd2fc8ed7b857","datavalue":{"value":{"entity-type":"item","numeric-id":2434738,"id":"Q2434738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"395cc0b166da04e4ade3b54505384ceba7746a95","datavalue":{"value":{"amount":"+0.8372925519943237","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":"Q643801$6675C66D-2618-4877-9A74-5DC9524ADD6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"229273036e93c8a2b57e4326c2a37b07088f8d4b","datavalue":{"value":{"entity-type":"item","numeric-id":5374000,"id":"Q5374000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce401fa4e253dea5e3a6cfd5f0c77707d2b41db1","datavalue":{"value":{"amount":"+0.8220306038856506","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":"Q643801$7F95DC97-4F94-4F3A-BB97-93A2365AF436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4200669362dbc9f0f9919e5bf2ee6727d703f95","datavalue":{"value":{"entity-type":"item","numeric-id":492278,"id":"Q492278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd128eb88878ceac80dddd8e69296ed4534b77c0","datavalue":{"value":{"amount":"+0.8196802735328674","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":"Q643801$5C9E14A2-2422-4FCF-85D4-22B1C710383B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b026d1bcbb21973bce0dabca547c4754e15db855","datavalue":{"value":{"entity-type":"item","numeric-id":3392127,"id":"Q3392127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9d98712ca92cfe250245cb8572315ab79a16293","datavalue":{"value":{"amount":"+0.8154299259185791","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":"Q643801$25C54BB5-F3E6-4774-B387-026E03AAFCEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:643801","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:643801"}}}}}