{"entities":{"Q1602710":{"pageid":1613450,"ns":120,"title":"Item:Q1602710","lastrevid":72305601,"modified":"2026-04-14T04:00:28Z","type":"item","id":"Q1602710","labels":{"en":{"language":"en","value":"New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1758393"}},"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":"Q1602710$5E77922F-D2DD-40F4-BE9E-39019A22293D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8b91343f2edbf42ee094a33e4ef6ba8235e2757","datavalue":{"value":{"text":"New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1602710$035B0C9E-1361-416D-A062-903EDB76BFE5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2531f3435e6aca5faf4d08320464c7a02ec4f2c","datavalue":{"value":"0996.90062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$A8EDCDF0-7AF4-4918-A9E5-3C21A3D32E00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"434f3ddef99625e2546181670f0bd5c1b196f656","datavalue":{"value":"10.1016/S0166-218X(01)00271-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$A3337DAD-C552-4900-BBE2-B6AC9F3E3898","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":"Q1602710$A6779091-A5D3-4167-95F9-32295493C5B4","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":"Q1602710$4DC54090-E0A6-4BE3-B20F-0350A7B5A022","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a534570e0971a78c1c6ea7df21b086e5c48a5c56","datavalue":{"value":"The following minimum cost connected multi-digraph problem with node-deficiency requirements ({MCNDP}) is considered: The input is a digraph~\\(D=(V,E\\uplus F)\\) (with \\(E\\cap F=\\varnothing\\)) a cost function \\(c : E\\cup F\\rightarrow\\mathbb{Q}\\) with \\(c(f)=0\\) for all \\(f\\in F\\), and a {\\text{node-deficiency function}} \\(d : V\\rightarrow\\mathbb{Z}\\) with \\(\\sum_{i\\in V} d(v)=0\\) and \\(d(s)=0\\) for all \\(s\\in S\\), where~\\(S\\) is the set of those nodes that are not incident to any arc from~\\(F\\). The goal is to find a minimum cost multi-digraph~\\(D^{\\star}\\) on a node set \\(V^{\\star}\\subseteq V\\) with arcs in \\(E\\cup F\\) such that \\(D^{\\star}\\) is connected, each arc from~\\(F\\) is contained in~\\(D^{\\star}\\) with multiplicity one, and for each node~\\(v\\in V^{\\star}\\) the difference between the out-degree and the in-degree of~\\(v\\) in~\\(D^{\\star}\\) equals~\\(d(v)\\).    The special case with \\(d(v)=0\\) for all \\(v\\in V\\) is well-known as the Rural Postman Problem (RPP), which is polynomially equivalent to the Traveling Salesman Problem (TSP). Motivated by a special case of the TSP treated by \\textit{P. Gilmore} and \\textit{R. Gomory} [Oper. Res. 12, 655-679 (1964; Zbl 0126.36006)], the authors consider the special case of the MCNDP, where \\(D\\) is a bi-directed path. For this special case, they describe a polynomial time algorithm that is an adaption of an algorithm for Gilmore and Gomory's special case of the TSP due to \\textit{M.-O. Ball} and \\textit{M. J. Magazine} [Sequencing of insertions in printed circuit board assembly, Oper. Res. 36, 192-201 (1988)]. Generalizing this special case of the MCNDP and modifying the original algorithm the authors obtain polynomial time algorithms for several other special cases of the MCNDP, including the wallpaper cutting problem and the warehouse order-picking problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$958C01B9-5D41-4894-9748-C77136F9F2BF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0cb2c52c0c371f86ece143c24c1b0b4fa619fbfa","datavalue":{"value":{"entity-type":"item","numeric-id":193593,"id":"Q193593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$66ED8E0B-C656-4B15-9821-613F4D003CCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$65CF6174-13B1-47AA-8146-27A6CF6E7B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$6759BCD1-330B-4BB7-9CDD-22790673F83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$060BF359-005C-4F56-A0DC-05EE6677A960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$6F82B25E-9699-4D37-978E-D56952BC59F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b78d856c3b08f961c7e2db6d0fa6b7c3827f1edb","datavalue":{"value":"1758393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$36250E05-156E-46EF-A8F1-DDB3B18056DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398999db83e6f0b9619e9606c6c09b8be1baa252","datavalue":{"value":"traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$4B852D22-614D-433B-AFF2-6D10E0FB647E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0907fcd5e10e2269870607556ba0a3cf46d0b79","datavalue":{"value":"special case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$DB59D505-2CC3-444A-8807-291267E9439A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e81f83acf92ff267f0120709014fc50f24dbd040","datavalue":{"value":"rural postman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$FE88048E-C50B-4228-8CA4-6BF925EF7735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38c9e99af27378cce25cd7d61e418e5e2a3c5cea","datavalue":{"value":"warehouse order-picking problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$24CE1E25-4A9B-468A-B11F-2A2E535332FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfed3a441ca3bcde5c536b26657df1f54e3c569e","datavalue":{"value":"wallpaper cutting problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$C4835F8C-0EBF-4416-ABAD-EC1C861D3212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f47f4be752dbc3470ea270cfbe9b5ba1756824a","datavalue":{"value":"minimum cost connected multi-digraph problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$07DE1C9D-6D5C-4D37-BD53-6DA7FA65D19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f8d43a5463c439058f48b710177a789735b6014","datavalue":{"value":"node-deficiency requirements","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602710$44012517-671B-4567-A21C-E0F16C14ACA1","rank":"normal"}],"P16":[{"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":"Q1602710$6F7EFB45-9BD5-4F2B-A6B8-853C3FE27FE5","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":"Q1602710$54D91812-4098-4A71-95C7-A1F2F666E025","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$352D2708-867D-4AED-8AB8-AFAE93C928EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42d3132d60d4734a6121b0d1472ed35fdcaa462e","datavalue":{"value":{"entity-type":"item","numeric-id":4210360,"id":"Q4210360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$26E9BBFA-AA16-4142-85CC-9D2159FE31F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6ba3760296387f683613ac96cd14489c78d128","datavalue":{"value":{"entity-type":"item","numeric-id":5657902,"id":"Q5657902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$BA021A97-5DD8-4257-844A-D23D2DB7A8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6580b367a8c77254b89faa8bd3605a5190689d8b","datavalue":{"value":{"entity-type":"item","numeric-id":4285636,"id":"Q4285636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$BC3DD06D-0F8F-430D-BF5A-30D410D58695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e9d9549e2e905e6d354f325a3b025d729afb215","datavalue":{"value":{"entity-type":"item","numeric-id":3141520,"id":"Q3141520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$6003D709-52AA-4AAE-98D5-C340CE0A5C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dcdf0c1c4fa44f70ae85ea37c6ee50907f4b72d","datavalue":{"value":{"entity-type":"item","numeric-id":5656371,"id":"Q5656371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$CF903E25-A13B-467B-9F89-4477A0F97764","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":"Q1602710$CFB0D879-0CBA-41CF-83A0-41603BD25DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de5e098f2b6e6238d033ffee7b1f35a44ae2bba","datavalue":{"value":{"entity-type":"item","numeric-id":4168391,"id":"Q4168391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$67C4FA57-44A9-4272-950B-B0214AA4D7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10d9726bd833217e3e0ca3cedd2d986dbf6d0d6","datavalue":{"value":{"entity-type":"item","numeric-id":5331678,"id":"Q5331678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$EE337C96-FCC7-4F47-8D23-0780815405F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f030d49769421de93ba4d8c53706308a5ef4c44c","datavalue":{"value":{"entity-type":"item","numeric-id":5187226,"id":"Q5187226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$A318213C-A512-41FF-86CD-0706707DA7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bede02fb916e2d1bb2a7ba2ce9bd0f4fb898f437","datavalue":{"value":{"entity-type":"item","numeric-id":1302599,"id":"Q1302599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$B76487C0-FDED-4A65-BA64-BDA1618516D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fb92d0c47be1223623b1854929572465a19ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3861175,"id":"Q3861175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$629732F6-A8D3-41B6-A113-564CDFA773EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dbbe3ac3158330a6990b58a9a558d77085ad86b","datavalue":{"value":{"entity-type":"item","numeric-id":4039868,"id":"Q4039868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$5E626DA0-B8C4-49D4-B0DB-3FAE7DA2453D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce8d8f1a1624709769a8a693e9a1bc1f953b847e","datavalue":{"value":{"entity-type":"item","numeric-id":3674397,"id":"Q3674397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$2163D4D8-C8FA-44F5-8C00-2B5938746E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d7a528b95772e4558bed4e20db5a587ddb1d0a0","datavalue":{"value":{"entity-type":"item","numeric-id":800829,"id":"Q800829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602710$F9012340-FA99-4609-9ADB-33BF608BFE42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95517a1455638ccb47dd5dd0dff2dd277e0d236a","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(01)00271-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1602710$3ECAA63A-0653-4D26-AA00-9F1ABFD711DF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c48b96fabe200f9395edae5743d8e0e8a660671a","datavalue":{"value":"W2059981036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602710$62C269C7-5EBB-40B5-9BA4-28345EEE6E76","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"048c428e820c5898cfd443eeb1329e08424eb796","datavalue":{"value":{"entity-type":"item","numeric-id":5753758,"id":"Q5753758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d850d3c3cbd3aef8c2879cfba3600d3f574f85fc","datavalue":{"value":{"amount":"+0.9393163","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$770F5E22-D825-484C-9BD5-35B71268031D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2183ddd95e2af31b90ed26a801a76c66ad2abd17","datavalue":{"value":{"entity-type":"item","numeric-id":1290165,"id":"Q1290165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1229a3ff7b23074fbf5400de28a23f08a95bd28","datavalue":{"value":{"amount":"+0.93226635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$DBEE24E6-C1AB-41B8-A054-9733DB54EB8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19d4607d60226fb86439d3339103f75619425d23","datavalue":{"value":{"entity-type":"item","numeric-id":2780838,"id":"Q2780838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f3adeffb36f255c3d55810aa5261310833a79c4","datavalue":{"value":{"amount":"+0.9268062","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$E5A86EF1-F5CD-4B3A-89C8-36BED8B89203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0723bd9d481f99f3a89b8bc03a7157fc1de133d","datavalue":{"value":{"entity-type":"item","numeric-id":1805008,"id":"Q1805008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a64db6a8d940742092a3fef06bc22c7d225fad0","datavalue":{"value":{"amount":"+0.9267758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$F22F65E5-1A46-4B8C-A177-E28B5C9086D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8f1442a3b5914831850ae7120cd5e9ac5d408b8","datavalue":{"value":{"entity-type":"item","numeric-id":5202515,"id":"Q5202515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55801f241686a84048c24024a26f22968c967758","datavalue":{"value":{"amount":"+0.9106731","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$CE9E388E-3E86-4E0F-A7D5-604DE06E54B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"471c6cda3da493efd2996279e3db8247854287b1","datavalue":{"value":{"entity-type":"item","numeric-id":3074625,"id":"Q3074625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dd9b246fec030620db356f6bd5c06088135bd3e","datavalue":{"value":{"amount":"+0.90552795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$B6046668-043A-4D6F-BCFB-2FE4A364A667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb7b1021946de140bf93e0a2dd0d110c758e39fe","datavalue":{"value":{"entity-type":"item","numeric-id":4347415,"id":"Q4347415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"797398d2e79644ddc4f358f4a727de76e2b171a7","datavalue":{"value":{"amount":"+0.9041971","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$C47005B2-A642-4569-9C9C-CBCCF7F6819F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db5b8405f9f875ea4d83f44cd30288f587c0e10f","datavalue":{"value":{"entity-type":"item","numeric-id":3973407,"id":"Q3973407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a63d76973ff560f62f602c6f106b639f3b5422f4","datavalue":{"value":{"amount":"+0.9020876","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$72D90092-16E7-4C04-AA9D-2D3D72C34760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68055330f1e777773fd911b7c3358a92e2f49fb6","datavalue":{"value":{"entity-type":"item","numeric-id":3059494,"id":"Q3059494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e171d932428ace897b73bfbe60ad0b3324d1db36","datavalue":{"value":{"amount":"+0.90072215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$E79BA0C7-A2A0-4AAC-A635-ED8E0771BC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a293228ab49c3b428299dd40de067c447b3ebfe","datavalue":{"value":{"entity-type":"item","numeric-id":3989345,"id":"Q3989345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8f0e1dfc9158eeea804028be7ece9b644aaac4","datavalue":{"value":{"amount":"+0.8981321","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602710$C6BA94E5-8130-4FED-B8D7-F9893E3A6D57","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization","badges":[]}}}}}