{"entities":{"Q687042":{"pageid":688891,"ns":120,"title":"Item:Q687042","lastrevid":47194405,"modified":"2025-12-31T23:31:25Z","type":"item","id":"Q687042","labels":{"en":{"language":"en","value":"A note on the prize collecting traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 429097"}},"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":"Q687042$45EADF8E-5AA5-46F3-82F5-4D6333190E63","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57e7c8f3d12cf12f9a7cb4cb76a512d35358f7c7","datavalue":{"value":{"text":"A note on the prize collecting traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q687042$00EA790D-14E1-41B1-A440-28A35747C547","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7df05583aaf210ed2ca12d2b71343725ecb46a1c","datavalue":{"value":"0793.90089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687042$D617C069-46A4-42BA-A6D0-70690278B0D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f4e2733a0a3e929be7cb2b488fc9429871674637","datavalue":{"value":"10.1007/BF01581256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687042$926B1A34-C89B-4402-8A8D-66D5CBAA4985","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb42abb4d03c24c0e42c27e662a950bd082fe46","datavalue":{"value":{"entity-type":"item","numeric-id":687041,"id":"Q687041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$096503D1-2048-47A6-BD50-160CF2DC8481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b31d559f2795e764965423307abc0e718f4695d2","datavalue":{"value":{"entity-type":"item","numeric-id":221942,"id":"Q221942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$A5FEFF78-AC97-4D9D-B05F-C5C2F6B864AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db91f50b8be0377b16c54636f8603d4272be2cda","datavalue":{"value":{"entity-type":"item","numeric-id":163023,"id":"Q163023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$2C2EEA19-3BC0-45E2-87EF-F36212711799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac7537c48c812c6b32a62e6d918beaeb90aa1eab","datavalue":{"value":{"entity-type":"item","numeric-id":324760,"id":"Q324760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$8BC39232-72F7-4D2F-85F9-0E52CDDB8F42","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":"Q687042$0BA48290-FECA-4F02-AA63-8C254730A4B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64a5597878452508c38f77062c2f388a61f673bf","datavalue":{"value":{"time":"+1994-08-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q687042$8B51033E-B3C2-4E50-9438-FAB2CB74BFA7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e762b5c24f85fcd79d7bda94edfb347f810dcb15","datavalue":{"value":"The authors are dealing with the following problem: given an undirected graph \\(G(V,E)\\) with a cost function \\(c(e)\\) on the edge set \\(E\\) and a penalty function \\(\\pi(v)\\) on the set \\(V\\) of vertices; find a subtour, such that the length of the tour plus the sum of the penalties of all those vertices, which are not visited in this tour, is minimal. Additionally, it is assumed that the edge costs satisfy the triangle inequality.   The paper presents an approximation algorithm with guaranteed approximation ratio 2,5. Unlike the Christofides heuristic in the usual traveling salesman problem, this algorithm is not of combinatorial nature but uses the ellipsoid method to solve a set of specific LP-relaxations (for each vertex \\(v\\in V\\), where \\(v\\) has to be visited) and finally the best of the induced feasible solutions of the original problem is chosen.","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$746ABB4A-24C2-4A17-B519-344C575B53B2","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":"Q687042$776AB5DF-DCE6-4ACE-B65F-25908C9FE8E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687042$DA0BA659-E735-44F4-B992-F3FC2B5E31C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687042$4D1D1D15-775C-4A26-A633-E2229B0C1D1D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"acecc4895558bb8428a3c959f45502c958b37985","datavalue":{"value":"429097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687042$00533926-6CBE-4248-B2C2-EF2799DE5DD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e39fea3dd361996673edc92f258b6ba8839669e5","datavalue":{"value":"vertex specific penalties","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$17A9040A-5BAE-45D4-8F1B-6F5063C70A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$B745AC39-B303-447D-9215-E926F9C11989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"904bc0b40ecaeb1024b7edfca483a8fff16bf888","datavalue":{"value":"subtour","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$57E454EC-4A5A-48CC-A40F-208722A9592E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$51B38400-31BC-4A6B-B4AD-D9CBE27E3DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1be1297d0cba74e39804d36d8fd022b372e11b15","datavalue":{"value":"guaranteed approximation ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$42C0289C-9D2B-486E-AD98-391C3FB8A3E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$5A8C8A0F-FBF0-472C-B013-D1673AEBFC84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"599981ae0f13000555cdfbe3e563d6ac043c85d5","datavalue":{"value":"ellipsoid method","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$4DA82C6F-DD00-4046-829F-5AA6D0787AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d7139df34657862114a6b0bd21017206b682e8e","datavalue":{"value":"LP-relaxations","type":"string"},"datatype":"string"},"type":"statement","id":"Q687042$B2A6D1A2-D6DE-470E-BC3C-E80AA15D34B9","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":"Q687042$0B17C34B-A9EB-4A9D-A3E9-FD45617638D2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b534cb0254ac7e53aa86fecf9ad7586d5f0111b1","datavalue":{"value":{"entity-type":"item","numeric-id":3832349,"id":"Q3832349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$6290A498-25EE-4B46-90E1-083A57237957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"861d68e5ce2f0698135e14e69e8cb3c6d612fdfb","datavalue":{"value":{"entity-type":"item","numeric-id":3138916,"id":"Q3138916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$C5E11B12-0709-49DC-B6C2-E923C262E420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73eb84a543b338a4a079febb7b97c03a91da92f","datavalue":{"value":{"entity-type":"item","numeric-id":5633847,"id":"Q5633847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$9264ECFB-2B91-4962-8E29-BAF28B419E7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c2b3c7fb3b376eb72f67f57977bbae27ac2eaac","datavalue":{"value":{"entity-type":"item","numeric-id":751989,"id":"Q751989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$C47A1EBC-BD98-4A9F-BF12-EC903F1EB2B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a8ace826b710cd9d35bd13f7615e7f800d7358","datavalue":{"value":{"entity-type":"item","numeric-id":4103563,"id":"Q4103563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$3D4BF078-9F81-4BC8-8C93-6D7754A876A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187c6bbf42d371cd0bf167be36088c4072cc9745","datavalue":{"value":{"entity-type":"item","numeric-id":912624,"id":"Q912624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$23D72478-6FF5-47DE-9690-18D844C9C39C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a9a11a507beacf09011d2ef5cfb746162eec76","datavalue":{"value":{"entity-type":"item","numeric-id":3885519,"id":"Q3885519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687042$E02F1505-391B-4EEE-B796-B95E527B0BEB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0822b9d004eeb1802569a7aaec226120049d68a","datavalue":{"value":{"entity-type":"item","numeric-id":3066163,"id":"Q3066163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5df3fed3d5e8ef02222be0edf047882a6c42955","datavalue":{"value":{"amount":"+0.8255465626716614","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":"Q687042$8182DF9D-91BE-4199-B1E0-58852DC5633A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46bda8924b82bc844f944fc731ee6b9f2086c154","datavalue":{"value":{"entity-type":"item","numeric-id":1944387,"id":"Q1944387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dce3ea0f53ea9a72d58644e5de12094b34053b3d","datavalue":{"value":{"amount":"+0.8200106024742126","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":"Q687042$1A18E726-7A90-44B4-ABDD-9700F643E1E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5d7968e083efbedc44c7d58944532f2b164aa9","datavalue":{"value":{"entity-type":"item","numeric-id":3832349,"id":"Q3832349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb8299499a9b5297eed6c0ae5c15384d38189bc3","datavalue":{"value":{"amount":"+0.8162192702293396","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":"Q687042$5046C1FE-FDB9-4E68-B183-23F2F5BD9F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836004b6729d8ddf61f9b05fb9cc38d0f057fc14","datavalue":{"value":{"entity-type":"item","numeric-id":3020008,"id":"Q3020008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cae18b336505f8dd7b90841222855dbd9fa3307","datavalue":{"value":{"amount":"+0.8105306625366211","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":"Q687042$18D86893-E1A5-475F-AFF0-462459665156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfc52d4890ed24e06d3805460f33fe0103866bb9","datavalue":{"value":{"entity-type":"item","numeric-id":3057103,"id":"Q3057103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f9c83e13df3a807f5a7a2e7b6542b024bc10559","datavalue":{"value":{"amount":"+0.8086288571357727","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":"Q687042$80FF4A3F-B7BA-4796-9DB7-D4D95200F66F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:687042","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:687042"}}}}}