{"entities":{"Q6875112":{"pageid":20747248,"ns":120,"title":"Item:Q6875112","lastrevid":84224885,"modified":"2026-05-13T19:49:25Z","type":"item","id":"Q6875112","labels":{"en":{"language":"en","value":"The \\(k\\)-Opt algorithm for the traveling salesman problem has exponential running time for \\(k\\geq 5\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8144546"}},"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":"Q6875112$F63219E4-DEEF-47A7-9A9E-806AA3434764","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"611e39dc9e3356b34d9eb2dc8a719fe167488787","datavalue":{"value":{"text":"The \\(k\\)-Opt algorithm for the traveling salesman problem has exponential running time for \\(k\\geq 5\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6875112$C89D721D-64EC-4E7E-A001-0650D342DE42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b59009c9948edeb71f334e42dfbb9eabc00977e","datavalue":{"value":"10.4230/LIPICS.ICALP.2024.84","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6875112$205E4211-6994-4AEF-A307-A6D7BD653E9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0bdddd7aa16843b9c1c70ca0eb31dd86fff5779","datavalue":{"value":{"entity-type":"item","numeric-id":6521266,"id":"Q6521266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$4B3C1C16-04FD-428A-8451-B90E535E5C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"52692bec4dd2c5f076a6d18eb2b28d1f9f813bff","datavalue":{"value":{"entity-type":"item","numeric-id":2055277,"id":"Q2055277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$F49C5BC2-46F9-4F7B-8FAA-9111A79E2D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"62ff535d2ba7354e7303f2e291d7bfd613cdf256","datavalue":{"value":{"entity-type":"item","numeric-id":495036,"id":"Q495036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$B610186C-41E4-46B6-B4C9-CF3C25389344","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b40aa8e8f7aa0bc84afc51f131ebe74b5bd0afe1","datavalue":{"value":{"time":"+2026-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6875112$97084E53-5FB1-4D99-B47D-C981F364ADD1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1a86519cb3571ebce07f2774b2a00a0f17e12c3e","datavalue":{"value":"68Nxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6875112$04F25ED1-9BE6-4AB7-999E-2944EBCDB86E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6875112$0E1E827A-94C7-4EFC-AE90-600E296B7E44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9778f96d266c57688a2781cb0139e5f5bb14b52","datavalue":{"value":"8144546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6875112$F7193C10-33E4-46E9-9A08-5BFDE175FB77","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$3D275C0C-B857-45D5-BEF8-BFFAF85044CC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398999db83e6f0b9619e9606c6c09b8be1baa252","datavalue":{"value":"traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6875112$DA77666F-E42A-4D86-883F-88BBB97274AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c08cf6cede53da64f99dad454862164d8fcec835","datavalue":{"value":"\\(k\\)-Opt algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6875112$72B83602-8B89-426F-B71C-277B9B6A4CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c60a1eef22a42dda092f07142dc0d97f60b76a1","datavalue":{"value":"PLS-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6875112$4417F65D-83DC-45F4-AD64-98E55C13119D","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":"Q6875112$0AD566C8-2CFD-46D1-B5E1-BACA3E0F66A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"34d4b8b57b4d7ed7bf52a0e660915171ee74a900","datavalue":{"value":{"entity-type":"item","numeric-id":4182679,"id":"Q4182679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$E50050EB-997B-4030-963E-63FCACD4B05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"757562158d73509af3220db5e5ba76d707908e02","datavalue":{"value":{"entity-type":"item","numeric-id":4268854,"id":"Q4268854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$04E5A88D-BA71-4F01-87E7-5ACCC948FEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc2b3f4f90c00a81d66c3d0543064cf52f16d2b9","datavalue":{"value":{"entity-type":"item","numeric-id":3576199,"id":"Q3576199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$FAFE8061-813D-49F5-8895-10EBE3C521FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc31c0253bff98b961a52a96e25b5cd164241658","datavalue":{"value":{"entity-type":"item","numeric-id":3012803,"id":"Q3012803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$EC9E4492-3FAA-4303-B51C-75D1AE216A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"081547e16f1958278fd39b1e3a5eb8d776523ec0","datavalue":{"value":{"entity-type":"item","numeric-id":2441587,"id":"Q2441587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$60DD5CCD-324C-4EB3-96B7-73A9ACB1810E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ddfb236c59ba17c8b0a52a945a31feef7521935","datavalue":{"value":{"entity-type":"item","numeric-id":1134626,"id":"Q1134626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$83065BA0-CD6E-446A-8466-FFEE440A1ABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12086856e478cd73734a7548be2a18f4ec58d978","datavalue":{"value":{"entity-type":"item","numeric-id":2558159,"id":"Q2558159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$E02DCBB6-5E49-42A8-9EA9-C940A2CF7F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c2e79c1e2d7d88de5ad5bdc70e2ca7168179d8","datavalue":{"value":{"entity-type":"item","numeric-id":4365133,"id":"Q4365133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$5D3C344B-7425-4B1C-93B5-045EC118F2CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"302adbaf2b8357f20069be2a0dab5e3eb2168585","datavalue":{"value":{"entity-type":"item","numeric-id":1109573,"id":"Q1109573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$E9A912F0-2E4A-483B-9AF5-2282ED7B3DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c255f2e6ecd34a611f1ccf928bf197acbeea63","datavalue":{"value":{"entity-type":"item","numeric-id":4051879,"id":"Q4051879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$2B90B22C-68A3-4C06-A6E3-4AED847FBA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3684b6925649f3b5db8b5557617873e0d87543","datavalue":{"value":{"entity-type":"item","numeric-id":3474886,"id":"Q3474886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$2D2B2DE4-83D7-471A-A57D-EE0938D87B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"142b7539a2ff7d00c0fd4ce4af15308e10e10086","datavalue":{"value":{"entity-type":"item","numeric-id":3587365,"id":"Q3587365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$1328FD11-E037-42EA-92BE-4A8119FB08B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c69bd88039fc2b5c466db49948d1fb8849c5e385","datavalue":{"value":{"entity-type":"item","numeric-id":3563008,"id":"Q3563008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$B379E642-5E93-4010-A116-47C837E35507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53a3daa9eb7c9604f5f70cc54ea4c2f7f49fc2a2","datavalue":{"value":{"entity-type":"item","numeric-id":4153924,"id":"Q4153924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$4C2EB1B7-0A25-4F9B-8B43-B5469D5D4303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e154aff975eccecff8ea8e44d6f9771213807b6a","datavalue":{"value":{"entity-type":"item","numeric-id":4016908,"id":"Q4016908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$39709A97-17E4-417C-909F-64026CDC7E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d45d601b8142b2e55e92dc0b64ae24b0029836e","datavalue":{"value":{"entity-type":"item","numeric-id":4852626,"id":"Q4852626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$A9ED6744-B03A-4968-90B8-1EB3E847C8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17f54e09132b99bd89721843b6f55072758b48be","datavalue":{"value":{"entity-type":"item","numeric-id":3204045,"id":"Q3204045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$CFC8BFE1-F8B3-49AD-8DBE-C01A22EF91FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d86c580a68833d4d99adfac31ee799661eb3d5","datavalue":{"value":{"entity-type":"item","numeric-id":4365127,"id":"Q4365127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6875112$304D9B4B-9223-4227-B7E5-6EA34C275C0F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The \\(k\\)-Opt algorithm for the traveling salesman problem has exponential running time for \\(k\\geq 5\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_%5C(k%5C)-Opt_algorithm_for_the_traveling_salesman_problem_has_exponential_running_time_for_%5C(k%5Cgeq_5%5C)"}}}}}