{"entities":{"Q1079133":{"pageid":1089885,"ns":120,"title":"Item:Q1079133","lastrevid":48956242,"modified":"2026-01-06T07:41:34Z","type":"item","id":"Q1079133","labels":{"en":{"language":"en","value":"Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3961372"}},"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":"Q1079133$01980F14-B902-424F-952E-0EBFA3B4DAF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"95acb4a48ee1f0875e36eeb5b5fb8c90cfc4d40a","datavalue":{"value":{"text":"Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079133$EFB39F95-8578-492F-88EB-EFEFA7851A11","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e21399cf44f6d0d056978f1088b2b348907739a5","datavalue":{"value":"0596.90093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$27D1BD42-E032-4B96-9F01-01338A12EA27","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab22a5e31ff156d056c974bf67ae183128a79dc7","datavalue":{"value":"10.1016/0377-2217(86)90140-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$EA870BB8-7C29-4CAC-BB24-DE228FEAFF41","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b969806e15667b8bb837290cff38032bdae579d","datavalue":{"value":{"entity-type":"item","numeric-id":242829,"id":"Q242829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$8ED93A5D-3CAC-4CBF-8E6C-15B19C55D89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11c1f1f9079d02ebeb6b8cf94e1bc627bd0842c1","datavalue":{"value":{"entity-type":"item","numeric-id":304237,"id":"Q304237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$408E8AEF-C64E-4135-A806-0F0C76C926A2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$B5696946-3EE9-41C2-94A4-38340AADFED2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1079133$FDA81E89-0DAF-4B7D-8BB3-17B5D3C5C710","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ef13b4ee4ed3ff8cf24a496ddf5328a5add5c8bd","datavalue":{"value":"The bottleneck cost of a routing in a complete digraph \\(G=(V,R)\\) with costs \\(C: V^ 2\\to V\\) is the maximal element \\(\\max_{(i,j)\\in r}c_{ij}\\) of the routing r. The authors are interested in minimizing the bottleneck costs in general and under certain restrictions (given a subset of endpoints etc.). Under the assumption that C obeys the triangle inequality the following results hold: (1) there exist (polynomial) heuristics, which guarantee solutions, that have cost no more than twice the optimum; (2) these heuristics are optimal in the following sense: if any heuristic can guarantee a (2-\\(\\epsilon)\\)-approximation \\((\\epsilon >0)\\), then \\(P=NP.\\)    The proofs crucially take advantage of the square \\(G^ 2\\) of an arbitrary graph G and the fact (due to Rardin and Lau) that it is possible to find a Hamiltonian cycle in \\(G^ 2\\) of any biconnected graph G in polynomial time (G given as input).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$198ED426-17C2-4413-8F5F-DA1617634F3D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$5264F229-FD93-4FE5-B377-323B76312BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$FF7EE9DD-7639-4312-9485-E3D1D8433300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$4B01098E-48BE-4839-AF6D-D3510AFBA3DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80f2894c325fe24a6f3fa8a109e29d2cb29aabba","datavalue":{"value":"3961372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$B1D22C4E-AA07-40B4-ACF6-72ECB75F9033","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb5a9c7e00e3e0a60ce1f321dc845779527523a4","datavalue":{"value":"combinatorial analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$E2756FE0-A200-4757-8823-9EFB64D7A13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ac0d050a4d8cd1183a4dab04b507fbb8dc43b8","datavalue":{"value":"transportation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$BAC2C49C-1584-495B-A417-D6A72F70AF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$B2B2C145-CAD2-4ADB-BE8B-B14C85F9C305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$F3C832CC-F59C-4AA2-91E4-3827B8BEDDC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2595ec503bfafdedfb1ee6282d0ca66ea6fdde1a","datavalue":{"value":"bottleneck cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$7E0DD3BC-C511-40CF-8D97-BF71D1E16FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9847b5080561732e2df3fe2a5afade2166808c","datavalue":{"value":"routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$D29AC994-BD97-4AE8-84AE-8C638AAF41EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff2ed59240f81cb0c06949a5dce2e4150bfc8f6a","datavalue":{"value":"complete digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$8B9EA4AD-E174-44A4-9F62-9BD3AD47CDAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$804F2FEC-E302-4149-9BCD-4A9C954A5468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$0C3516E6-5EF2-4995-A0B7-21A5CFDDE5A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079133$C27D9BE6-5586-4D42-9A30-0222A423DA92","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$A8C2C613-FDE3-407B-8336-EDF5114E7634","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":"Q1079133$CC5601C4-016F-4A06-88C1-8313DE4FE242","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"72954d0828c8abf9cfe2287d9c29b531796cad8b","datavalue":{"value":"https://doi.org/10.1016/0377-2217(86)90140-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079133$6D13D4B1-A074-4420-802F-44DB44EC02E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf30714ede82f8fbeda0841851d3e829f9ce5c78","datavalue":{"value":"W2034037360","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079133$AF57B989-2FA5-4202-888A-A7F661F71399","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$70F32F12-8BBC-48E2-8479-18CC8477A026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e71248ceac88560dd8f57b403457ee33d58bf0be","datavalue":{"value":{"entity-type":"item","numeric-id":1393413,"id":"Q1393413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$FD58622D-0282-4B69-AF1B-F2054A6A4C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae31c7e7985e437133bb613f2b43e812c25a499","datavalue":{"value":{"entity-type":"item","numeric-id":2558870,"id":"Q2558870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$BBF862B7-BD39-4522-AF9C-7AE1AE607E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b99f23c21d3771a98a9f9662331f20e4d3e99c","datavalue":{"value":{"entity-type":"item","numeric-id":3725544,"id":"Q3725544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$C791AE61-54B4-40AA-A22F-5F0F06727E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d83e8521729b3d9f10b76e29d08a81700d93efc","datavalue":{"value":{"entity-type":"item","numeric-id":3680584,"id":"Q3680584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$6FCF273F-FF8D-45A4-9DB4-B9D3FBAD1D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1069e50b068ef018915247d74050582991afa6","datavalue":{"value":{"entity-type":"item","numeric-id":1150378,"id":"Q1150378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$2678D187-B422-49D9-A5CD-7C617702C93A","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":"Q1079133$701F6DF1-2A22-4DBB-97E7-AF4D2D06E704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e102855d78129e98165e69c7b981008f149840c","datavalue":{"value":{"entity-type":"item","numeric-id":3956421,"id":"Q3956421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$E618526D-3486-468F-A601-6B6501DF24D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0b4954d58c1eef2d85e4792d01c7e288c21b38","datavalue":{"value":{"entity-type":"item","numeric-id":786658,"id":"Q786658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079133$597B311E-1404-485C-997A-CD39DF7138DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40b5cd46fff15dce15ee9da9cee4c02e93a0a59d","datavalue":{"value":{"entity-type":"item","numeric-id":3328310,"id":"Q3328310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24723c0c355d9cece8ac3af1add4262a789643e4","datavalue":{"value":{"amount":"+0.7980303168296814","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":"Q1079133$49C9A9F8-C965-4FC0-97E6-A724D6CA6BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6135721dbb3f3eeec8faaa50c76ea618cdc663eb","datavalue":{"value":{"entity-type":"item","numeric-id":519098,"id":"Q519098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74158320b4f69b446d4b2547429c5e0dd0b2bdb7","datavalue":{"value":{"amount":"+0.7859408855438232","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":"Q1079133$BF3B97B6-76CC-4F94-B75D-37C991A65F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16839f8d7afa32e845d012089fba5eb0fe5c063e","datavalue":{"value":{"entity-type":"item","numeric-id":336878,"id":"Q336878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2c2b0b86d1e2ae77c8f3b09f1f1dc31a28fe6b7","datavalue":{"value":{"amount":"+0.7834688425064087","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":"Q1079133$A9BB02F7-4EBC-4710-A479-19D359DE2808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"306b64ad72be68f677fb8ee5b4dfce074ac84dc3","datavalue":{"value":{"entity-type":"item","numeric-id":2269075,"id":"Q2269075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"432f6dd8f7d9b2ec9c0b03fe0cafcbd18963fc69","datavalue":{"value":{"amount":"+0.7811158895492554","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":"Q1079133$BEC7BEF1-FDC3-4BE7-A11E-202F26CB5AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"834b95b66d678b606fd905d813343329d65a1158","datavalue":{"value":{"entity-type":"item","numeric-id":1180833,"id":"Q1180833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"600f0e0ccd80ab937a08f887989544de821f91c2","datavalue":{"value":{"amount":"+0.7656117081642151","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":"Q1079133$6CCA0B98-A937-4B09-A89A-355FEB75389D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1079133","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1079133"}}}}}