{"entities":{"Q1774146":{"pageid":1784888,"ns":120,"title":"Item:Q1774146","lastrevid":48472609,"modified":"2026-01-04T22:34:00Z","type":"item","id":"Q1774146","labels":{"en":{"language":"en","value":"New approximation results for the maximum scatter TSP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2162505"}},"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":"Q1774146$50481A64-3B5E-4847-B68E-37DB8A364EBA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"457c507513e73f4be8189d90b00a4ce09e41bb1d","datavalue":{"value":{"text":"New approximation results for the maximum scatter TSP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1774146$8B492532-EC29-4E19-8FD6-FAFBBFE9230A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f169e20835f10e5d639a4738de931eefe270347c","datavalue":{"value":"1070.90136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$4F54FEB7-D906-4F0B-A2D8-93A94C60E15D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"19a600025d6d465db089a0a9cb9d2410d31db3d4","datavalue":{"value":{"entity-type":"item","numeric-id":705552,"id":"Q705552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774146$3814A941-3F65-43DC-B0B2-68B59AB6970A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774146$F241B74F-0732-4B4F-AFDA-56DAD2AB1511","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cfdd76c6ace7e0d57b8524faf2ffe47b441fd852","datavalue":{"value":{"time":"+2005-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1774146$8971340A-CA77-4292-A1D7-7748290E8005","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3c419d1c2bc45e10fbb1fcad204658aa572c06a","datavalue":{"value":"The author considers the maximum scatter traveling salesman problem: There is an edge-weighted complete graph \\(G\\), find a Hamiltonian cycle such that the length of a shortest edge in your cycle is maximum. The problem is also known under the name max-min 1-neighbour TSP. In the max-min \\(m\\)-neighbour TSP the problem is to find a Hamiltonian cycle (path) such that the minimum distance between any point and all of its \\(m\\) neighbours on the cycle is maximized. The poblem in general is NP-complete and no constant factor approximation exists unless P = NP.   The author gives an \\(O(n^2.5)\\) time approximation for the max-min 2-neighbour TSP with triangle inequality. The paper contains a factor 12 approximation for the path version and a factor 18 approximation for the cycle version The author describes new algorithms for \\(n=3k\\) and the path version and for all cases of \\(n\\) and the cycle version and the remaining cases and the path version. Two new algorithms for the case \\(n=3k+1\\) in the path version are provided. There is also a \\(O(mn^2.5)\\) time algorithm that achieves a constant approximation factor of 16 for the path version of the max-min \\(m\\)-neighbour TSP for certain values of \\(n\\) and \\(m\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774146$EE87F8D5-BAAB-4A6B-8930-7717E14D7F97","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"23765cb9a36703caa352c60ca99b87123750646f","datavalue":{"value":{"entity-type":"item","numeric-id":193684,"id":"Q193684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774146$3EFFF48F-8838-48FD-B4C3-E05AFCB395DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$A9CCD4DD-127E-4E35-A5AE-213431A4A6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$7F040E1B-8A1D-4A5F-A926-6A602D1CBAFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"967faa5e4b3822b781c0ec760c32ca03190c1a2b","datavalue":{"value":"2162505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$9F076FEB-351C-49D3-BFC5-ED829E19F779","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22dacbaef8a4f8d80a666aea3501722dc1ab720","datavalue":{"value":"TSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774146$DAD74F25-EBFF-4BF7-85F1-BD1970219334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dd16b6f68c9cec754317ec0756192f05e11f789","datavalue":{"value":"maximum scatter TSP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774146$276A07CF-BF44-413E-AFC9-32382601F982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774146$139212BE-2D69-46BF-9305-2B62B44D4585","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":"Q1774146$14EEA1DF-FED6-497B-A5B8-8052AEE67719","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3775af7c983adf2418f243922b64ae9662ac8668","datavalue":{"value":"https://doi.org/10.1007/s00453-004-1124-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1774146$C01692BE-7250-4730-90DA-6648CB7CBD47","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e2bcabb3714060767eddd5d943205425dddd4473","datavalue":{"value":"W2004512957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$854599EE-FB1F-4088-B1C7-DAE4173ADE55","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"571bbf93228fff4af2266b6452fca2e6e7b0e5f6","datavalue":{"value":"10.1007/S00453-004-1124-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774146$C2F89D3E-4792-47C9-ACBF-548EE921AA1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6e63412f2615ab02c5d266fd3a390b140d27800","datavalue":{"value":{"entity-type":"item","numeric-id":4268895,"id":"Q4268895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df0fd953abb9a6cda2f7fef109db80c7fe9f4fff","datavalue":{"value":{"amount":"+0.9131044745445251","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":"Q1774146$945B80AC-7A45-41DF-8E49-51BF0EBFCC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d533a5b8633fd80da8f73a29264ef34559e509cd","datavalue":{"value":{"entity-type":"item","numeric-id":4575744,"id":"Q4575744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecc62a1a5a3c3c05283bd875296c1b0477ab6502","datavalue":{"value":{"amount":"+0.8319976329803467","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":"Q1774146$9B0425F4-A03D-490A-B993-BA3C4FE62B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f5c555a05c5923f2e53e4e67d620fd6c5796a06","datavalue":{"value":{"entity-type":"item","numeric-id":4596195,"id":"Q4596195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad3784ca3fb86ca3afc79f1365ae3ac6f41e8cb7","datavalue":{"value":{"amount":"+0.7865464091300964","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":"Q1774146$2903D02E-8ACF-42DB-A1EE-33A20255D689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d89ca7e8c49191eb53ecf7821703a4815f776cd","datavalue":{"value":{"entity-type":"item","numeric-id":4458874,"id":"Q4458874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2197bea7b1d8b63ae2094cf11199dde8b4a3bbdb","datavalue":{"value":{"amount":"+0.7848533987998962","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":"Q1774146$D7FA4651-B0A7-4D62-96FE-6715BCCD7078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"444d90f9f5734e9ef40c8e11a6803ce63aaaf3e2","datavalue":{"value":{"entity-type":"item","numeric-id":2768270,"id":"Q2768270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cf02fcb7c6e7d240b0e798137619e8d3a9e4647","datavalue":{"value":{"amount":"+0.7791771292686462","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":"Q1774146$9F380C13-BE2B-4D7D-93CA-84710806A663","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1774146","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1774146"}}}}}