{"entities":{"Q492278":{"pageid":494045,"ns":120,"title":"Item:Q492278","lastrevid":52328405,"modified":"2026-01-21T11:21:18Z","type":"item","id":"Q492278","labels":{"en":{"language":"en","value":"Probabilistic analysis of an approximation algorithm for the \\(m\\)-peripatetic salesman problem on random instances unbounded from above"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6474026"}},"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":"Q492278$95F79F4C-DA40-4532-B769-E81C9D1014BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35198c0d53bd90dbd5b7a77beaa2b756fbcae4f6","datavalue":{"value":{"text":"Probabilistic analysis of an approximation algorithm for the \\(m\\)-peripatetic salesman problem on random instances unbounded from above","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q492278$60F6EAC5-DA26-4560-95E5-8B87FF08C8AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2cbd5c717590d5253a5ea238c421d3f50d3826e2","datavalue":{"value":"1336.90073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$86D7AD34-33BC-4868-BE7B-E30FD02B81F9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1dc4a4c39efe6b38ab96d2077be47272652c8c16","datavalue":{"value":"10.1134/S0081543815050077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$053DAC81-C557-40DF-A0C4-3D101806E2D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9146186d5fb5ea8967079aad42a3aece79a3d57f","datavalue":{"value":{"entity-type":"item","numeric-id":492276,"id":"Q492276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$09270D73-4DF2-4C9A-9FA0-7D11F5973A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"81d0bf849d48645ccb5e959a6657a6948b3aedd7","datavalue":{"value":{"entity-type":"item","numeric-id":294360,"id":"Q294360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$69DD5AD2-A83E-4AED-B595-408AAF3ED78F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec7e849eaea7db917c8576ed0ed859451c3ae439","datavalue":{"value":{"entity-type":"item","numeric-id":492277,"id":"Q492277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$D541DB55-C5FA-4BC9-9CFE-452790A0386C","rank":"normal"},{"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":"Q492278$A704D663-8515-42D7-BE7F-E92260AFD9CD","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":"Q492278$311FCE5A-790A-4F0D-A23F-692DE468595E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8e39592c2ba32aeaf9bbb43265ec41a1bb013153","datavalue":{"value":{"time":"+2015-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q492278$161B81C4-50CA-4104-8752-78F29F4FA9A7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"df37ba64b4488ee97795f29e1a51c518baa8c7db","datavalue":{"value":"Given a graph \\(G=(V,E)\\) and \\(m\\) different weight-functions \\(w_{1}:E \\rightarrow \\mathbb{R}_{+}, \\dots, w_{m}:E \\rightarrow \\mathbb{R}_{+}\\), the \\(m\\)-peripatetic salesman problem (\\(m\\)-PSP) with different weight-functions is to determine \\(m\\) edge-disjoint Hamiltonian cycles \\(H_{1}, \\dots, H_{m} \\subseteq E\\) with minimum (maximum) total weight \\(W(H_{1}, \\dots, H_{m})=\\sum_{k=1}^{m} \\sum_{e \\in H_{k}} w_{k}(e)\\). The authors consider the special case where the elements of the distance matrix are independent identically distributed random variables with values in an upper unbounded domain \\([a_{n}, \\infty)\\) with \\(a_{n}>0\\), and the distribution is normal or exponential. The algorithm presented is a modification of the algorithm ``Go to the nearest not yet visited city'' and it has the time complexity \\(O(mn^2)\\). It is shown to be asymptotically exact if \\(\\beta_{n}/a_{n}=o(n/d(n))\\), where \\(d(n)=\\)ln \\(n\\) for \\(2 \\leq m <\\) ln \\(n\\) and \\(d(n)=n^{\\theta}\\) for ln \\(n \\leq m \\leq n^{1-\\theta}\\) and \\(0 < \\theta < 1\\). Here, \\(\\beta(n)\\) stands for the parameter \\(\\alpha(n)\\) or \\(\\sigma(n)\\) of the exponential and normal distributions, respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$3CDB1FCB-AC57-430D-9E38-88F60F9AB569","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$5A7A9AA8-7FB4-47BD-8745-F76D71FF11A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$00ACE9E0-73A2-4C12-9BF0-E82787DBFDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dade3bc82a2f7e555fdd92f6a7aa24c002fcafaf","datavalue":{"value":"90C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$F472F6D7-35CE-4013-BAA1-5F3B46D40625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$EEC8F574-F323-4429-9D1B-91846B436DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$403546E5-3C9E-4B11-A8F3-06EA4AAC0B30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4befc846d68b5c0e5669379cd0d7b86678e64395","datavalue":{"value":"6474026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$A3E6A3C6-A7A5-4EAB-8E8A-CDB23C2716DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"765fc668963209dbd34b07a4c58c43a376d6262e","datavalue":{"value":"\\(m\\)-peripatetic salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$41D548DB-C7F5-444A-B635-7C160BCFC12C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$5547E206-7661-492A-9823-726B694B4AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$62B7F979-4520-4EA1-8B72-EBE76C093ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10db8fb859c85795509962c81d4d3015099e0f90","datavalue":{"value":"asymptotic optimality","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$B04DCF32-76DD-4880-B873-7A8089D2B3A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6357a5116e554ab6ce2c7e353fa907bd8bd61cd","datavalue":{"value":"random instances","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$5F0021FC-EFC5-4CE0-8B8F-65AEEB8329FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d84aed947d32e1fb3152a3196e6debf9578a5567","datavalue":{"value":"density function","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$F51D2A80-C962-4483-AF60-78554BB10988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfe3e346bc375a23665b6d14d5d656667716e669","datavalue":{"value":"truncated normal distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$3ACB7AB0-3044-4D00-8C1A-CBC457E43DBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"819af648045a04de32da229bcb679989536405ed","datavalue":{"value":"exponential distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q492278$7451AF1D-B69A-4973-9A4E-21C1E6B55543","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":"Q492278$BED876B5-371A-4421-A019-A081108E1448","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36705645fa238d039eac8b9a91cb2094c84bf6e3","datavalue":{"value":{"entity-type":"item","numeric-id":1310005,"id":"Q1310005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$A968FB93-4C93-4D34-9DB3-6C4437A8F858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd8a59d18a10c533526724b15bf7b046a5cff594","datavalue":{"value":{"entity-type":"item","numeric-id":5704203,"id":"Q5704203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$97EAB1C3-4538-4B1D-9D51-150FAA0EEF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ed805d18452617f73d9c2e5163a926020503d33","datavalue":{"value":{"entity-type":"item","numeric-id":3416558,"id":"Q3416558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$37F5024A-5451-4DBB-800F-F8A32515E631","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc5c4a3ccc58988ee37a4759f7295f20fe792e5","datavalue":{"value":{"entity-type":"item","numeric-id":4068472,"id":"Q4068472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$43BA0A05-7118-4961-9FFA-6BA0B8B33534","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":"Q492278$E62A74FC-FACC-4EE2-A728-3D095D55290B","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":"Q492278$B77B5F21-778D-4F9C-9183-3A7E15C0C7DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a369dacddce9180c38da64c07dfd6969f4311cd","datavalue":{"value":{"entity-type":"item","numeric-id":643801,"id":"Q643801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$59A24EE5-588A-4BB8-83C9-0918011162D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27104398bca794e5dcf9433c0dede439b2adf3bd","datavalue":{"value":{"entity-type":"item","numeric-id":5264723,"id":"Q5264723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$203ADCBC-62C8-4522-8E84-4786D2E8A26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0271ea010b369d236887a1b6d0bf89e55007499","datavalue":{"value":{"entity-type":"item","numeric-id":4187615,"id":"Q4187615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$A178C350-7D75-44F6-A5BB-2C6004BCD9D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$965811BA-D574-4C81-ABBA-619963F79842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c39629a6aa0188477f6ee3db843fdcacf05b57b","datavalue":{"value":{"entity-type":"item","numeric-id":3757055,"id":"Q3757055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q492278$7D54620B-5E30-4955-B507-AB26FBAB9387","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36de240c43a636ab2a9c836272fdbc1dd5fb2a5e","datavalue":{"value":"https://doi.org/10.1134/s0081543815050077","type":"string"},"datatype":"url"},"type":"statement","id":"Q492278$48EF9911-5755-45EE-AE5E-EE839C65CF0F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eea12045d5fca20601e68a8d54ed067b2af13d64","datavalue":{"value":"W2473151934","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q492278$C06E447E-DEA2-4942-B7F6-9F2A8B2FC991","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fc48ee4796cfdac0368073b15eb9ccc7a2c28f7","datavalue":{"value":{"entity-type":"item","numeric-id":3115676,"id":"Q3115676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1bf40fa25b19b81ab593640e7f3e01590bb3af7","datavalue":{"value":{"amount":"+0.8601569533348083","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":"Q492278$5EEA12EF-4EAE-4864-97AE-F50B5C05EEA0","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":"f598c9c5c30ee3e1d844244aa47721bc351c502f","datavalue":{"value":{"amount":"+0.8572878241539001","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":"Q492278$7AB10ADA-29A6-4BEF-8FEC-09A864B77893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7374f81cd5d7418c14b0ade1f636f9d547b29cb3","datavalue":{"value":{"entity-type":"item","numeric-id":3133207,"id":"Q3133207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86dae6c9bb6d98ca7196a2cc998a53f849ecec40","datavalue":{"value":{"amount":"+0.8454489707946777","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":"Q492278$D0796EA2-1E51-432F-ACA0-C14F499A35EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eb38cdf68f61f08fec9e33011988ab70900decf","datavalue":{"value":{"entity-type":"item","numeric-id":4852853,"id":"Q4852853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f0c6b7fc599cbbf21720a0a6e8d40fad776e767","datavalue":{"value":{"amount":"+0.8404370546340942","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":"Q492278$AAE36803-5324-45FB-802F-1E795A96B0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23a0dedd2335f726bea0e4081486f7e0be4a64f5","datavalue":{"value":{"entity-type":"item","numeric-id":3115278,"id":"Q3115278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60eaffe377d90bff2d14fbf0d78097108ac32fbd","datavalue":{"value":{"amount":"+0.8309905529022217","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":"Q492278$6B795252-D0BD-4360-B813-BFD0DA252669","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:492278","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:492278"}}}}}