{"entities":{"Q1281349":{"pageid":1292099,"ns":120,"title":"Item:Q1281349","lastrevid":46601700,"modified":"2025-12-25T04:36:55Z","type":"item","id":"Q1281349","labels":{"en":{"language":"en","value":"A generalization of the convex-hull-and-line traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1267368"}},"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":"Q1281349$5F214651-B3A7-4C8B-92F4-CE22B7FCDC66","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6e9d8666cb060cd741b8fdbd1b3739921476ee0b","datavalue":{"value":{"text":"A generalization of the convex-hull-and-line traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1281349$7B4A0829-7EE4-4AF0-B4F2-BC3179375001","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb375a04b028b628b749e40fc284b1e5ab506284","datavalue":{"value":"0918.90131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1281349$77EBFA45-DB10-4B3D-B2C3-7DB840096D0C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ed65f8601a720e7274bc26624fb8fa48158efd6","datavalue":{"value":"10.1155/S1173912698000108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1281349$CD9816B4-EB3A-40B0-B057-D6A7616A8F71","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d127085f944eb24026719a2a4a849158864c3044","datavalue":{"value":{"entity-type":"item","numeric-id":86285,"id":"Q86285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1281349$D8001E02-9CED-47B6-A19D-A23DEE2FF125","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c8655680bfd79de85fc3b27d4412f09e07e944d","datavalue":{"value":{"time":"+1999-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":"Q1281349$46A8EF87-68C1-4475-8A77-A245FEFA4848","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd4a7bc215abe8cfbb272ee52da72acea22b8ead","datavalue":{"value":"https://eudml.org/doc/119876","type":"string"},"datatype":"url"},"type":"statement","id":"Q1281349$E8A66027-A2E8-4544-8F9D-B298B913E019","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f316fe0a8fde30f449bc7c6affa6ba8b96ad9ec4","datavalue":{"value":"Summary: Two instances of the traveling salesman problem, on the same node set \\(\\{1,2,\\dots, n\\}\\) but with different cost matrices \\(C\\) and \\(C'\\), are equivalent iff there exist \\(\\{a_i, b_i: i=1,\\dots,n\\}\\) such that for any \\(1\\leq i\\), \\(j\\leq n\\), \\(i\\neq j\\), \\(C'(i,j)= C(i,j)+ a_i+ b_j\\). One of the well-solved special cases of the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solution scheme for this class of TSP given by \\textit{V. G. Deineko}, \\textit{R. van Dal} and \\textit{G. Rote} [Inf. Processing Lett. 51, 141-148 (1994; Zbl 0806.90121)] to a more general class which is closed with respect to the above equivalence relation. The cost matrix in our general class is a certain composition of Kalmanson matrices. This gives a new, non-trivial solvable case of TSP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1281349$09680822-77F0-48CC-A7F9-C20679BCF48B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1281349$3A325B5B-78BC-4595-B651-4EB338CD4941","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb63de1eb41a1549c2055e3009d32588d64cfc40","datavalue":{"value":"1267368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1281349$4781C7BF-BB2D-481A-A198-AE788D1C72A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1281349$FD4FBE01-BB41-49BE-88F6-E53938E2BB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1281349$8C9E4B1B-8585-4227-B262-AFF091EC8ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9bf2c12a3f7acf216926d0be84f6b1e7bc3729d","datavalue":{"value":"convex-hull-and-line","type":"string"},"datatype":"string"},"type":"statement","id":"Q1281349$DD14E0F6-E2EF-4A9C-B2E2-8233FE0B4847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6182c88e08560e656aa7cae3def36147c5bbbd79","datavalue":{"value":"Kalmanson matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1281349$D7D59B7E-57A1-4501-AFFA-588B63F5DFD8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3adc7aa0a8580111f5cf34b1e5d4de90e87979db","datavalue":{"value":{"entity-type":"item","numeric-id":867919,"id":"Q867919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1281349$FBBAFC55-6161-490F-830B-D81CB9DB3D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e220435c00b29aa44bd23746fb69b285a27bc9c1","datavalue":{"value":{"entity-type":"item","numeric-id":429678,"id":"Q429678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1281349$DC95FA27-DD01-4278-B578-BABAB5B991F1","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":"Q1281349$FBE09EC0-92EE-4062-B5B6-6F6902C78A36","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f557fc5fc68b95cdd02d72cb70250db6731d251a","datavalue":{"value":{"entity-type":"item","numeric-id":1350909,"id":"Q1350909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a8f773ee975a90fdfc17aac5da93422eaa506ec","datavalue":{"value":{"amount":"+0.8393182754516602","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":"Q1281349$B0EE3859-73C5-4EB2-9452-C0AB9CE67CE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89f017929ac85083131c531979fd27d4ce4e2720","datavalue":{"value":{"entity-type":"item","numeric-id":1332749,"id":"Q1332749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cdd108a69c84d8b295a744de07cf7afc937fd64","datavalue":{"value":{"amount":"+0.8301645517349243","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":"Q1281349$5A9CBEB9-3320-4866-9F36-B5CA235F04E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8c6d7d64d0f3c543d25ee0000324842232c4999","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75a697c133bc4ab880bdc29a440a79402ff69eb6","datavalue":{"value":{"amount":"+0.7874056696891785","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":"Q1281349$1533111F-256B-4785-8AB2-2427E487677A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"406f92d44852bfc2b094668bc9472448ba60afab","datavalue":{"value":{"entity-type":"item","numeric-id":1367695,"id":"Q1367695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"370cf8bb64c876728d915662841f3d37d7f35980","datavalue":{"value":{"amount":"+0.7781906723976135","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":"Q1281349$A8BCAB12-DF7B-4B4C-AC76-4ACD8D81BEC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e42e0d55579ddcc787d15ad0b2f6f0409a55b69f","datavalue":{"value":{"entity-type":"item","numeric-id":1080781,"id":"Q1080781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d6af90969dca8c339bc9136c63fb7fb80b515e4","datavalue":{"value":{"amount":"+0.7723838686943054","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":"Q1281349$FC36E27B-C4E2-4946-9409-E080F716C236","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1281349","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1281349"}}}}}