{"entities":{"Q635520":{"pageid":637368,"ns":120,"title":"Item:Q635520","lastrevid":63156315,"modified":"2026-04-11T10:59:11Z","type":"item","id":"Q635520","labels":{"en":{"language":"en","value":"An analysis of the extended Christofides heuristic for the \\(k\\)-depot TSP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5941238"}},"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":"Q635520$1013F0B8-51A9-4121-A457-5D7D53C6C456","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d8cfa7b547322ae02850cc722b16a11ebafa57b","datavalue":{"value":{"text":"An analysis of the extended Christofides heuristic for the \\(k\\)-depot TSP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q635520$76CC8D37-C96C-419E-8C5A-22B3EE2192CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"563c6e5bfce3d9a0253b94a6130fd149aacdbae5","datavalue":{"value":"1219.90149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$AE334C55-37CE-4948-BCCD-F6A5D3E90DB8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c176f9daa51f0b7254f0287ebe90af82ef865b1","datavalue":{"value":{"entity-type":"item","numeric-id":322547,"id":"Q322547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$806DD67A-840C-414C-B221-E545BDEAF367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b99c39089553a7ad2f79c209ab19d5356433c41c","datavalue":{"value":{"entity-type":"item","numeric-id":313238,"id":"Q313238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$CEB705F5-8D24-41F8-88CA-8A1DA300A46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dc5efaa97e701275c831f8c578d700b28723f37","datavalue":{"value":{"entity-type":"item","numeric-id":505185,"id":"Q505185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$028375EB-A8A2-430B-BA57-9EAD5375B39A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$25400429-D221-48D4-9248-D59267871D8A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c9973b58de11bddbd329b1cc3e6e49b7db7b7641","datavalue":{"value":{"time":"+2011-08-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q635520$49C2D54C-B3FA-4884-8A76-E472EED41910","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$E62F97BF-2381-441E-8122-7BA3A5C1E97D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$77175F5B-8797-4743-BE14-88A0358AB44D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de38e634c90e3ed94c624d93e0162f8f684bbda4","datavalue":{"value":"5941238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$DFB1FA58-B6CA-41B8-B5B3-C8176F5BA559","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q635520$AF1B8B71-E273-491F-8A20-B862CC48977C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"481d188558519fc133849490e450ee918f6633e4","datavalue":{"value":"Christofides heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q635520$4E6580C3-B3F0-433B-92A9-14C8C60D807D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c4b21e3aafe48ea9ea7a1ff2fb820f4d7f56fb","datavalue":{"value":"multiple depots","type":"string"},"datatype":"string"},"type":"statement","id":"Q635520$5DF6B690-C7F7-4D8F-A2BD-FF1C6DEA37A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22dacbaef8a4f8d80a666aea3501722dc1ab720","datavalue":{"value":"TSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q635520$5BF9CDC1-1AA0-4C59-8830-A081526F53A3","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":"Q635520$33ADA4D4-4B20-4FF9-B535-46AA228191B2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f3f70c02a52b5ebcba821d388e7d7156ac2f507","datavalue":{"value":"https://doi.org/10.1016/j.orl.2011.03.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q635520$42EFBF88-4902-4E2D-9ABE-049AE20BB54A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d41612d1deb379e50544c283faaddf05e31de48","datavalue":{"value":"W2056897184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$0BD2F442-3538-49C4-B4BC-27C0FEE3759D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d19d55a041c3565436b4fdbcf4db8345adee7049","datavalue":{"value":{"entity-type":"item","numeric-id":5491457,"id":"Q5491457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$A8B39B96-4C95-40B1-ABEE-FF680060F4CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b42b3d629c91eab2ad5ec169455ab027861a576f","datavalue":{"value":{"entity-type":"item","numeric-id":4849324,"id":"Q4849324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$CBF79734-5B76-4BEE-B7E8-B6095683F661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2560d53a52b3b2586bee3e8365b8a5a3d11616dd","datavalue":{"value":{"entity-type":"item","numeric-id":1357774,"id":"Q1357774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$93659B6D-CDBA-4210-9E01-ACD3AD53661E","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":"Q635520$F8E32664-1DC2-480F-8EBE-1800ED1E77A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e36e6d5e0f70ae691bd873e224082eaa77389fa","datavalue":{"value":{"entity-type":"item","numeric-id":4656714,"id":"Q4656714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$04007E55-8343-4C97-A014-82A8121D01EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c56ba874d01a6ee3cb23102ba6f1363706f2861","datavalue":{"value":{"entity-type":"item","numeric-id":5920350,"id":"Q5920350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$E224E7FD-D0D2-4633-A53B-E7479F1AA55A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a92e3476341eb53150986dc40a13f80217831bf8","datavalue":{"value":{"entity-type":"item","numeric-id":2467447,"id":"Q2467447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$1F64AFA0-29C3-4C0B-BF54-0D311E1531C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755016f5d3a8d2377ca1d607187ccf49a4dd096f","datavalue":{"value":{"entity-type":"item","numeric-id":2270326,"id":"Q2270326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$BFE5CA42-817F-43EA-9290-7380A0535C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e72c059339c6f9bfd7c86b4281799c75ace2202","datavalue":{"value":{"entity-type":"item","numeric-id":1919200,"id":"Q1919200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$CB0B04F9-BB68-47B2-AF2C-9288EC20A4E3","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":"Q635520$C49661D3-03C5-4A35-ADF6-C65158A45209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bd8ee8d61a16c209465ed7a21904cb2559ea5f8","datavalue":{"value":{"entity-type":"item","numeric-id":1026674,"id":"Q1026674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q635520$4C6A41CC-8F35-42BF-8B52-A24BCE78ED60","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd4953ab8857878d152be1e7aebc7231c3ca8503","datavalue":{"value":"10.1016/J.ORL.2011.03.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q635520$1FFCF71B-970D-4B83-8B48-B1CF11E0A2A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4d9e493a8c4e336d829034d6b01eff00679f906","datavalue":{"value":{"entity-type":"item","numeric-id":1752857,"id":"Q1752857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38a7c519842197811de0e34d0b7ddaed35fdc48e","datavalue":{"value":{"amount":"+0.9160067439079284","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":"Q635520$47106B39-24A3-41C3-BE28-DEB101A055CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00f9afe17ee3fadbca0164840033d1bf8efbb4ff","datavalue":{"value":{"entity-type":"item","numeric-id":2802244,"id":"Q2802244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a6d41e262ff15ff6d930bf4a900fabfc57b22ca","datavalue":{"value":{"amount":"+0.8741129636764526","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":"Q635520$D86639F8-C6BB-4227-8EF2-CD47C5F27EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d54a7ca9968acb88f09be6960d29e1677dddcb35","datavalue":{"value":{"entity-type":"item","numeric-id":3569885,"id":"Q3569885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec2b5f8c68014047b5d6081ac8406863f4776bf9","datavalue":{"value":{"amount":"+0.8412171602249146","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":"Q635520$8E528ECB-8D96-4708-B75D-17548023CF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2b40be26d424a8a91ec266bdc82858efbacc7f3","datavalue":{"value":{"entity-type":"item","numeric-id":2128771,"id":"Q2128771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45d42620fd62a9c638654f0a939c38a6c49e5c39","datavalue":{"value":{"amount":"+0.838702917098999","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":"Q635520$3AA7ECDF-1714-4933-9BAE-A66F121CAB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"859fdcd52884f3264ad990c0db58222451fec560","datavalue":{"value":{"entity-type":"item","numeric-id":691417,"id":"Q691417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57591929303ec19e8ce197774eb7d36319e6567","datavalue":{"value":{"amount":"+0.8063668012619019","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":"Q635520$F3CBD9DD-B663-42D0-8B3A-AB407D9B195B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An analysis of the extended Christofides heuristic for the \\(k\\)-depot TSP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_analysis_of_the_extended_Christofides_heuristic_for_the_%5C(k%5C)-depot_TSP"}}}}}