{"entities":{"Q2043355":{"pageid":2054097,"ns":120,"title":"Item:Q2043355","lastrevid":57700602,"modified":"2026-03-31T23:36:12Z","type":"item","id":"Q2043355","labels":{"en":{"language":"en","value":"Shortest paths with a cost constraint: a probabilistic analysis"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7377177"}},"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":"Q2043355$BC0EF3B0-3D22-467F-8B8C-F4BECC0DBA2F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2e69bf8de5bc1058e340c5d2b2f4d486a810b82","datavalue":{"value":{"text":"Shortest paths with a cost constraint: a probabilistic analysis","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2043355$F4348835-E943-4ACB-9651-6DC837F9CD4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"975a93c87f6fffbaf6f0718777f8d28b4f384467","datavalue":{"value":"1492.90186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2043355$307B9499-0096-49A5-873A-AE067E84423F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b27515d469dfd012c92fe2f2c18443f1b26d0ee","datavalue":{"value":{"entity-type":"item","numeric-id":375760,"id":"Q375760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$099E903E-3E15-4196-A7B8-D26A757165A3","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":"Q2043355$5765D1BB-651C-49FD-B0DE-AD67CC9D48DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$E02FCE7D-7E47-4EA4-9EF9-C027D4334AFB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9b5760f38c083b2f10e5de93ad782280e507f608","datavalue":{"value":{"time":"+2021-08-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":"Q2043355$A3D66D3E-54C9-4560-BAD1-DA001D1FE71E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"042d6f87dff20ec3487a746045a47f891a8bc142","datavalue":{"value":"https://arxiv.org/abs/2005.12241","type":"string"},"datatype":"url"},"type":"statement","id":"Q2043355$71F30F36-008C-4CEE-A2A9-CCEDBF61A30E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e9c1aa37275eb46245efdcf1dcc7a3cc4dbc348","datavalue":{"value":"This article starts from the concept of complete graph \\(K_n\\) and its set of edges. Let us given an independent random edge \\(e\\) having the length \\(w(e)\\) and random costs \\(c(e)\\). Having given a budget \\(c(0)\\), we have to find a path \\(P\\) from vertex 1 to vertex 2 of minimum length \\(l(P)\\) and the total cost \\(c(P)\\) less than \\(c(0)\\) if \\(P\\) denotes the set of paths from 1 to 2 in \\(K_n\\). This approach is a well-studied problem, at least in the worst-case.  In this paper, the case is considered where \\(w(e)\\), \\(c(e)\\), are independent random variables and let \\(L_n\\) denote the random minimum length of a budget shortest path, \\(H_n\\) denote the hop-count (number of edges) in the shortest path. The authors assume that \\(w(e)\\), \\(c(e)\\) are independent copies of the uniform \\([0, 1]\\) random variable \\(U\\). In the first setting of this paper, they establish an asymptotically correct estimate of \\(L_n\\). The outlines of the article are: an estimate of \\(L_n\\) in two distinct ways, a lower bound of \\(L_n\\) and using Lagrangian duality, another bound is obtained. The final consideration of the authors is that the duality gap between the maximum dual value and the optimal value of the solution to the constrained shortest path problem is within \\(o(1)\\) of the optimal value to the latter problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2043355$5144554D-9EB1-4EA9-B206-2C5E1A8D37E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"39ab04d50f4acfcb668d65dc15063009855f3e58","datavalue":{"value":{"entity-type":"item","numeric-id":593139,"id":"Q593139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$0F2A3785-99DA-4598-8BD7-88B40E894B83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2043355$F4966358-989A-4022-90B7-CFCCDC601FBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b522e1bca19143da91c6231d79f1dbfb1ec45a12","datavalue":{"value":"7377177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2043355$7B8447D6-329B-4B18-A030-9D9D2D1EE3D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6013c41b5873e050a2bb366d742631baceaef4b1","datavalue":{"value":"random shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2043355$58BA8407-5B80-4862-96C4-272582618E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b45cce68aae19cf5b51a183e6e2530c17637641a","datavalue":{"value":"cost constraint","type":"string"},"datatype":"string"},"type":"statement","id":"Q2043355$A60AD086-5472-4A97-AFD2-EF7473976E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58870da1a411fbaea967c29271b1a9178ff50ec1","datavalue":{"value":"weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2043355$7A0B6AA2-6402-4087-B098-94416DDE538B","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":"Q2043355$199752E7-FBA8-404C-9266-A9483F44EBB7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a557c558bae17f038ae35cffa81ec34b9e7c2d2","datavalue":{"value":"W3173650023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2043355$098B433B-446B-4285-9CC8-8B82F57E15C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa69518ad5390dd3b7eacd1dfdf190322860b61","datavalue":{"value":{"entity-type":"item","numeric-id":2428045,"id":"Q2428045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$213B2D17-CD2D-4738-A1C4-E5A5B8442CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56bdc7393d96deb79df2cd0e70ba5713cb41a2ac","datavalue":{"value":{"entity-type":"item","numeric-id":5917572,"id":"Q5917572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$84FB87BD-D06B-4973-9677-F1D6B5656C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c8e362131bc4b4eadac329d5d30f6b5a576b77","datavalue":{"value":{"entity-type":"item","numeric-id":1166423,"id":"Q1166423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$EBC22589-9FC7-4644-955C-E8C6B1D13118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f21f2a2100a484c550be51b46d5687d5052d1dd0","datavalue":{"value":{"entity-type":"item","numeric-id":2223474,"id":"Q2223474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$23D39AF1-7807-49DF-93E0-78C924608A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e533e28b1cbb6bbefe7a2c796f75a2e3665a8b0","datavalue":{"value":{"entity-type":"item","numeric-id":4719434,"id":"Q4719434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$17C448F9-43D8-4BE0-9C19-ED665A1EB87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"775be623541c5213dd9e61e7f95c2a1417a8f404","datavalue":{"value":{"entity-type":"item","numeric-id":439323,"id":"Q439323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$EF4E7941-2D58-4A24-A970-940BFEA6C248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a54fc1ae027f3451649baa290357f1a8f2be94ce","datavalue":{"value":{"entity-type":"item","numeric-id":3115910,"id":"Q3115910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$FEEE36B1-12AC-4315-BFEE-0A31FCFAB7B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d42dbc4a00ff3c0fcda1293dd1ecab6559f97c8","datavalue":{"value":{"entity-type":"item","numeric-id":3649590,"id":"Q3649590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$AE2759C3-1DF3-4374-87F4-803AEFA99C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebf1f106049145fc706c7ea29a3e572ce636fd13","datavalue":{"value":{"entity-type":"item","numeric-id":2379862,"id":"Q2379862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$2C6E5DFA-0038-4C5F-9AA8-2B1554A23B44","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"88c3165f13bf5c87f8ffdc750a3ee48520189d83","datavalue":{"value":"10.1016/J.DAM.2021.06.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2043355$DFB49B07-7189-4649-B230-ED3AA95183C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4e45c3932c6546d7f998271dec2005bbc8dc624","datavalue":{"value":{"entity-type":"item","numeric-id":2223474,"id":"Q2223474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d77ed448f3aa94a9fb25c8c2015fec478da720c","datavalue":{"value":{"amount":"+0.844861626625061","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":"Q2043355$17E9D6E3-667E-4CDE-96EE-9862AD9AC566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"850376f0f1ae05d477554a52b0b841bb9d528591","datavalue":{"value":{"entity-type":"item","numeric-id":1113810,"id":"Q1113810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5382b801fa3ea9884a2aee4e97c845b1513cc600","datavalue":{"value":{"amount":"+0.8104240894317627","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":"Q2043355$50AD5CC9-D056-4E1B-8889-917A8D0A7692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1b9ffabeeb7e2a2a224e42a3b041b10eb238290","datavalue":{"value":{"entity-type":"item","numeric-id":3699721,"id":"Q3699721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c5976fcb297ff7a4d6a5e0e4693bca787d49d7b","datavalue":{"value":{"amount":"+0.7999511361122131","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":"Q2043355$4E230708-D69D-487D-A9D6-5E979DC91FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0fcc2cde6dd5ebfa451e538f6dbc5a4bf14afa7","datavalue":{"value":{"entity-type":"item","numeric-id":4952841,"id":"Q4952841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c6ec3f7ea9f0b1fb8a255ae62a651aba9d7c5b9","datavalue":{"value":{"amount":"+0.7819786667823792","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":"Q2043355$F59E9F2F-307C-4A52-9A7A-36C2515CEF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"151d7d3bf3185309dc5ec41f72009d734b940ccd","datavalue":{"value":{"entity-type":"item","numeric-id":491594,"id":"Q491594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36fc9d88029579de9e43b479973168484f62165e","datavalue":{"value":{"amount":"+0.7806847095489502","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":"Q2043355$F413AE23-6921-4A7E-97E2-868A5C90BC16","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2043355$410A6D93-FAD6-4C0E-9E17-1D406473513D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2043355","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2043355"}}}}}