{"entities":{"Q1602705":{"pageid":1613445,"ns":120,"title":"Item:Q1602705","lastrevid":47934202,"modified":"2026-01-03T03:08:43Z","type":"item","id":"Q1602705","labels":{"en":{"language":"en","value":"Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1758389"}},"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":"Q1602705$A0EA4804-5666-4B5D-B5CB-B4A8EF025DF1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c700d76abc8755326959e7d5f992ac6a31a004d","datavalue":{"value":{"text":"Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1602705$79D6251B-8B81-4464-8E20-F1AFE54A7607","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"220a9bef2112172e8030925c9d0bc11f4950072a","datavalue":{"value":"0996.90061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$DA647562-138A-4BFD-A807-C670EBE509CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fdd66a926e4d1ddd00bd7b83d2e6efd36ab2791","datavalue":{"value":"10.1016/S0166-218X(01)00267-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$988CD96D-5202-4AC9-9F3E-935830B4FF07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d62d1b98a8e47330bd8d09b4c364147d7b3d1f6","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$4960EAE7-1864-47D0-BE23-C5BB6968090A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$26A14451-B619-4170-B89F-12D770592315","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$F3E1EF3A-3180-4A1D-BF8B-9490CDB961A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1bdd63e74125a64b52265510548f082cbef9c284","datavalue":{"value":{"time":"+2002-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1602705$7B07FBCA-8F8F-4336-87D1-D9C48CE4C4D3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37c9b9cfb5aeadf0376f8c044c6aa706b3f48729","datavalue":{"value":"Using derandomization, the authors present the Greedy-Expectation Algorithm (GEA), a general polynomial approximation algorithm for combinatorial problems. For the TSP with \\(n\\) vertices it leads to an approximation algorithm with domination number at least \\((n-2)!\\), that is, there are at least \\((n-2)!\\) tours not better than the one generated by GEA. They mention that, in particular, this disproves a conjecture of \\textit{F. Glover} and \\textit{A. P. Punnen} [J. Oper. Res. Soc. 48, 502-510 (1997; Zbl 0882.90124)]. For the quadratic assignment problem (QAP) the GEA leads again to a polynomial approximation algorithm with domination number at least \\((n-2)!\\) provided that the number \\(n\\) of vertices is a prime power. For QAP they show that for all \\(\\beta>1\\) and every sufficiently large \\(n\\) the domination number is at least \\(n!/\\beta^n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602705$F18A7628-64CC-4DA9-A732-13EEC5B87FA3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5500d0e3ae3870dfabd55c7acf03571be7dc260a","datavalue":{"value":{"entity-type":"item","numeric-id":1018087,"id":"Q1018087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$BC8E7797-A864-4B00-9864-978FBD396945","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$D9FCC251-D43B-4E74-B3F7-19EAAC305583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$F72B3F1F-F661-4E64-B648-B62B24CDDCF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$C46AD757-3175-4133-86AB-3FCC9A97D96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$7CA346B4-1CC9-407C-B295-08BAB2D52EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$4BE45BD9-4E83-4DD1-9A40-16F8943EADC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$444E01FA-1F17-4949-AFEC-38FCCB25FAC9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69cae670672e589ec03c0101ca48bab4d71e2c38","datavalue":{"value":"1758389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$F88D8FF0-9ADA-480F-9057-13C7C4842378","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602705$2F0EA2CA-18F2-4BB1-885C-9D24B2E3528E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58ff8e8cfd34e94b2ac9a5d60bd899481f04e4dd","datavalue":{"value":"quadratic assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602705$DD69C542-EA7C-4802-9B46-87F2313F36AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602705$BEBE57A8-72E0-4F09-BBB8-7018FFE7BA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602705$2B55AA46-0381-45A6-8744-115B95FCBCDD","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":"Q1602705$89F057D6-8825-47F9-9C47-5AF9ECF36C06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$7DF4B49A-A626-4C2A-ABA6-40CF899059DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a93f13262bc300fba769190aafdb0940400641e6","datavalue":{"value":{"entity-type":"item","numeric-id":4888749,"id":"Q4888749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$357270F3-1D4E-44CB-B3DA-2CE13D47D6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b230f5557126ba4844c80a54ed8455c3d600d0cb","datavalue":{"value":{"entity-type":"item","numeric-id":4645932,"id":"Q4645932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$6C84874F-279C-4AAA-8C28-BE2F522CC17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f335709cafac8ad70fda23558eac5858cccfcd82","datavalue":{"value":{"entity-type":"item","numeric-id":2757553,"id":"Q2757553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$C0F5C841-054C-40C6-9A59-973EF08FE2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3cf8961986ffcaba70540ab5fb1760d13c405f7","datavalue":{"value":{"entity-type":"item","numeric-id":4664539,"id":"Q4664539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$33BF11C9-2C94-4B08-B3DE-225506AD9A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666261474c9625949f651c962cde2d1f630ea4ba","datavalue":{"value":{"entity-type":"item","numeric-id":5202515,"id":"Q5202515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$6A77F2DE-AC88-4710-BF80-07E378821F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08193ba46cd90270662a721fcc24f6a44eb8aeb1","datavalue":{"value":{"entity-type":"item","numeric-id":1377989,"id":"Q1377989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$5EF83F3D-BD96-48FA-B733-AE5DC2FD2BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5009df9c2650d54601861f947f8157b16561e492","datavalue":{"value":{"entity-type":"item","numeric-id":1575073,"id":"Q1575073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$FB344C1A-C558-4BFF-ABED-B783E7ED5B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72d240fe9610b207fa118424a3249d1d7c9c0236","datavalue":{"value":{"entity-type":"item","numeric-id":1917273,"id":"Q1917273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$BE216715-FDE8-4FA4-AFE7-30D4F03DA5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5127e25381c5abdfc870e919678600eb8b88e913","datavalue":{"value":{"entity-type":"item","numeric-id":5928379,"id":"Q5928379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$741E45A8-B97C-495A-B5AB-343AD6A711C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305990cab47347d26b508880daf4599932710fd4","datavalue":{"value":{"entity-type":"item","numeric-id":4347415,"id":"Q4347415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$383D9A45-2243-44CD-8ACB-03A63DE89400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0603e209bc2c65199cd27ad284915c29390bd9","datavalue":{"value":{"entity-type":"item","numeric-id":1302597,"id":"Q1302597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$C996CE2B-9FB0-4C9A-BB1A-AB0559A53614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25d9f8f8116e4c4092d8523e564337cfe67f89ed","datavalue":{"value":{"entity-type":"item","numeric-id":1602705,"id":"Q1602705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$1DD7C11B-0F91-4118-8131-9203477D3EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d640cba425e46b41669f9dbe12fd2d0d9d66380","datavalue":{"value":{"entity-type":"item","numeric-id":2529473,"id":"Q2529473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$677F39FB-5904-40D6-9ADC-0CC9A4E80DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89324d361b37a034b5349ba872fc20e8e4a8c32c","datavalue":{"value":{"entity-type":"item","numeric-id":1112724,"id":"Q1112724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$997EC8D9-6C54-421E-8364-446B157A2019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45f79f84a1fd111865cc5a25ba85a372c1b853e1","datavalue":{"value":{"entity-type":"item","numeric-id":3321154,"id":"Q3321154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$7110B510-0872-4DDC-9934-530893439472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f889b70f98fb8529870b5c9b2b581be1f5cae620","datavalue":{"value":{"entity-type":"item","numeric-id":1142224,"id":"Q1142224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602705$F94E2B3F-0F62-492D-B5DB-8B67BB24D43A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1d0d717487d9d22e1720f621f14957e1264a2ac","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(01)00267-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1602705$66386C4C-F3C4-4120-9893-5F68E25F6623","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b48da2d00541ed0e6fdfe5fb36663544187da65a","datavalue":{"value":"W2072269936","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602705$E231ECBB-0752-4905-922A-A8B95D9CA9D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43aae229f8ffede1c1309f187af2d84dd265b3be","datavalue":{"value":{"entity-type":"item","numeric-id":2811158,"id":"Q2811158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5d5fcf7e2873b016576c177f43d49dcff33b815","datavalue":{"value":{"amount":"+0.7686150074005127","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":"Q1602705$66BA4AA0-F000-432B-847C-FCEDD562923C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9e735ab9036bb05e5358095b5a0b401956a273","datavalue":{"value":{"entity-type":"item","numeric-id":1566378,"id":"Q1566378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6590f308b4d9ec03e65aff9d9d118fdb0667fb7","datavalue":{"value":{"amount":"+0.7487264275550842","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":"Q1602705$E76A99FD-71FF-4F3B-A2CC-557F94EC6E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24673d17188347e4317844b7ac1a683c2077dd21","datavalue":{"value":{"entity-type":"item","numeric-id":1602706,"id":"Q1602706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5164fa2aaf85fbc8b2713b97d06abccc58ac7085","datavalue":{"value":{"amount":"+0.742988109588623","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":"Q1602705$CD35B691-A030-49C9-8549-14B90E78B837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281343a9024732da9b8b8132d027b5ca28154c6d","datavalue":{"value":{"entity-type":"item","numeric-id":5939600,"id":"Q5939600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a96a5fa142cbee621bfa101a61c4be2a8852ee48","datavalue":{"value":{"amount":"+0.7429326772689819","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":"Q1602705$4A661D2D-7402-4740-8150-ABECFE1FD068","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1602705","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1602705"}}}}}