{"entities":{"Q1124707":{"pageid":1135456,"ns":120,"title":"Item:Q1124707","lastrevid":69698445,"modified":"2026-04-13T08:47:38Z","type":"item","id":"Q1124707","labels":{"en":{"language":"en","value":"Submodularity and the traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1370756"}},"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":"Q1124707$414E38A8-A7E3-42EC-883E-63A67EB11668","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9de1168a6022d512d004a72b159eaee3ad71977a","datavalue":{"value":{"text":"Submodularity and the traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124707$BF053B9B-2069-4475-A4C7-AC92D5B10C3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b63da285fb13f326cebbaa7ffa360e82242c1762","datavalue":{"value":"0947.90120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$6AB992B8-DDDC-42F6-955D-80C20BB18A3D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"603e56b1493391b724f9254eaf7cb0f860b0550c","datavalue":{"value":"10.1016/S0377-2217(98)00175-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$642E73D2-EA49-429F-BD48-5A1F0AD9FE56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10581da265f38c75fc78d320cd2d11d6707a18a1","datavalue":{"value":{"entity-type":"item","numeric-id":319461,"id":"Q319461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$B2C4A22C-46F2-4BF6-9FC1-6211129247A0","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":"Q1124707$E040A7FD-9A7D-46DE-98C2-B6134268899B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3f29977b3c78240439e6d7adfdac0711f36ba14f","datavalue":{"value":{"time":"+1999-11-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1124707$E010205C-86D0-4B58-BE57-2B8E34C94B18","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e77f9d0c4180e29829e7709ca55523039918040d","datavalue":{"value":"Consider a central warehouse and a set \\(V\\) of retailers. For \\(S \\subseteq V\\) let \\(T(S)\\) the length of an optimal traveling salesman tour through the retailers in \\(S\\) and the warehouse. The problem investigated is to find a submodular function \\(K(S)\\) and a small \\(\\alpha\\) such that \\(T(S)\\leq K(S)\\leq \\alpha T(S)\\) for all \\(S\\subseteq V\\). It is shown that there exists no constant \\(c\\) such that \\(\\alpha\\leq c\\) for all planar graphs modeling the connections between the retailers. However, when the facilities lie in the Euclidean plane the problem can be solved. Heuristics for calculating submodular functions are presented whose error grow slowly with the number of retailers. Computational tests show that the submodular approximations of the traveling salesman tour lengths have much smaller errors than the theoretical worst case analysis indicates.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124707$3CB3C2C5-C908-45FD-A281-3F4B9070EA3C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"647403b42bff8e5868a53244a891290fdc1b119f","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$2EE92F88-80D7-4FA9-B046-3E843CE0E500","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$1CC39754-9E13-4335-B39A-B27B1872B9D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$597E4927-FAB8-4D09-ABF1-E47D7602B9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"810d660658648f9bc3138c1cd0aba8029bb9050c","datavalue":{"value":"90B06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$18FED182-F194-47DF-B485-AE3779D771D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0b4c77eb9a725da30e5141cffa0edca743c3da5d","datavalue":{"value":"1370756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124707$13F89E4E-5E7B-4462-B2A6-55CECCD97FBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398999db83e6f0b9619e9606c6c09b8be1baa252","datavalue":{"value":"traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124707$27CB73CE-A640-4458-B2FD-CBC10A8F2D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124707$86D696B8-8AD8-4BC2-A66C-B5E26519010E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ce6d3e05c67e7e482c47120f2d05461bf865564","datavalue":{"value":"submodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124707$CAD06A90-18BB-488F-BF1C-5038613651DC","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":"Q1124707$DAECCAC2-CBA3-41F9-A3BA-404866239C2E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"69e8dbb18fce363ee55ee1f4b579d35c1ec9e85b","datavalue":{"value":{"entity-type":"item","numeric-id":3470228,"id":"Q3470228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$1C85D6D2-017B-4F0B-A6FB-DCDB9176A31D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d47fa6214894c3bf2d0d9847f974baa6104efa3c","datavalue":{"value":{"entity-type":"item","numeric-id":3686500,"id":"Q3686500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$592DDAE6-ECAA-4FF5-BFD6-D9C1A673D9A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5330224c0efc6f1107ad36463bc3b9056f6538ac","datavalue":{"value":{"entity-type":"item","numeric-id":5906501,"id":"Q5906501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$703994DE-0DB0-4A87-B24B-FD1AB2BD67F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ecbadb905930ae081fb4980e3c5f1fcc21a123","datavalue":{"value":{"entity-type":"item","numeric-id":5729634,"id":"Q5729634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$57FD56FD-7C77-4A4D-B0AF-4258D0FBBF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9e8a2a2ba09a34750ac91787a928d451826bfdc","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$47BD3F07-F96A-4F30-937C-1E49CE1B7E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$DC420E49-759D-438D-A7BA-506655BFD71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d877ac56c441756e2508c23f0d2c1e4241a02d6","datavalue":{"value":{"entity-type":"item","numeric-id":4027784,"id":"Q4027784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$385A3984-0C99-4283-88CA-C9E4000AFB7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"616fd337be358f72ecbd5fb15280bf1136f48c0c","datavalue":{"value":{"entity-type":"item","numeric-id":3228026,"id":"Q3228026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$364C95EE-FB42-4E9C-9753-D95AF368CA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f925aefd9c962b62195e63bd5ee29583f160cfe","datavalue":{"value":{"entity-type":"item","numeric-id":5378674,"id":"Q5378674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$23676FFC-0271-4496-B707-6F1EAB6E37AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4960d97c11c0cd0f282650fb582b7cd310577033","datavalue":{"value":{"entity-type":"item","numeric-id":3256638,"id":"Q3256638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$6B854E17-3705-4346-B51F-35CF46999963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03f95738dfaae069d9245a752169956722dee1eb","datavalue":{"value":{"entity-type":"item","numeric-id":1962020,"id":"Q1962020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$192B15C3-4F1E-4A5B-AB13-5C4B9DFFEEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c29fe475f3b6236fa6e6c0f6f81b9f9702cd9915","datavalue":{"value":{"entity-type":"item","numeric-id":1961984,"id":"Q1961984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$97AC87ED-8807-465D-B1BC-7EFCA2795B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e823cb0f4c3000cf6f3d35301b45f9f40211483b","datavalue":{"value":{"entity-type":"item","numeric-id":3705193,"id":"Q3705193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$9077F5AB-9565-4372-8280-CE9B0DF9EEC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$DC5DD172-2E49-44D3-95B3-F95E83C2FE94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f22d714e5a00aa78aab22769f51bb45ec60e3e66","datavalue":{"value":{"entity-type":"item","numeric-id":4327639,"id":"Q4327639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$A3A0B177-AA0B-45C8-9EAC-419D3270255D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acf1deb628926afade174d80c04b02501cadc4ba","datavalue":{"value":{"entity-type":"item","numeric-id":4367268,"id":"Q4367268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$6D541204-3EF1-46FF-A3EB-7AE0E7710631","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e3ba5483492c031df6abf13984dc5b904be57f8","datavalue":{"value":{"entity-type":"item","numeric-id":1357781,"id":"Q1357781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$73BD4B9A-E840-4A77-9977-5EF0E3D6EBBB","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":"Q1124707$7F67256F-0459-480A-8AE2-1A2DF477282C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27cb1e839cc2ec3f96759c01e6ee5d53eebb2552","datavalue":{"value":{"entity-type":"item","numeric-id":4268710,"id":"Q4268710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$145F9877-4932-4BF8-AE94-7280642DFA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9524d11e3548fa2018d0863de095cec92224865","datavalue":{"value":{"entity-type":"item","numeric-id":4152030,"id":"Q4152030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$2E656A07-5930-4C26-84E0-8F49DB7AD736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8596bf5b34b4f9c4a3a58cba55665044ddddcd48","datavalue":{"value":{"entity-type":"item","numeric-id":3474889,"id":"Q3474889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$CD2967E7-E13B-4D94-B2EF-53365DB658C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"474e2e6a82efc90d6ce5c5148de4104ea9695f49","datavalue":{"value":{"entity-type":"item","numeric-id":4140001,"id":"Q4140001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$274A2242-018E-411E-AF2B-F61CF77E0366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0731694373e42ffb6daff5d846709e3a1787bc","datavalue":{"value":{"entity-type":"item","numeric-id":3724059,"id":"Q3724059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$2D896520-054A-4794-959F-06D00CB6EC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73d3d075fb159bd2a5fddcde9c8c33beca2bf2ba","datavalue":{"value":{"entity-type":"item","numeric-id":4721065,"id":"Q4721065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124707$6FF863CF-2A79-483A-91D3-20C02B224B8E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0adff11c7c3ad9b96c86aab65f702621fd7a164f","datavalue":{"value":{"entity-type":"item","numeric-id":1116903,"id":"Q1116903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce3e0fd30c8caaa6da9eba0f5f8ba686f227cda1","datavalue":{"value":{"amount":"+0.7671157717704773","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":"Q1124707$142F903A-3CA0-41C1-9509-1B2DB5CCF692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5647ec692008ac2638684fe67702fe98e50f74e6","datavalue":{"value":{"entity-type":"item","numeric-id":4327639,"id":"Q4327639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa4ee3ebdaaa68e7b76fede630d3ae89ecbd3cd8","datavalue":{"value":{"amount":"+0.7530233860015869","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":"Q1124707$DDCA2C7D-4A28-411C-95A8-4A1B46A9AD80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8e6ddf02b31c47757bc6379641da47086932b68","datavalue":{"value":{"entity-type":"item","numeric-id":1099066,"id":"Q1099066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c00a5c02ac20c37a27336794eb9ba0674803a04e","datavalue":{"value":{"amount":"+0.7484689950942993","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":"Q1124707$821F447F-84C9-43BC-B384-9E5B3551F202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989c04bf82204d9c4f258df667b337206aaff748","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d81c25c1a97ce1065de7de207f1a97575767e611","datavalue":{"value":{"amount":"+0.7460350394248962","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":"Q1124707$355A56F1-A7C5-4851-B415-02F6214F61E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e444ff1e5dea6d3cb0c4f303db5cb242c5b22c76","datavalue":{"value":{"entity-type":"item","numeric-id":2345604,"id":"Q2345604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eaf5c6746755c1dc771cda5db44385dec443d11","datavalue":{"value":{"amount":"+0.742180585861206","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":"Q1124707$CE2E6390-20C8-405D-B59E-5254D5652D82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Submodularity and the traveling salesman problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Submodularity_and_the_traveling_salesman_problem"}}}}}