{"entities":{"Q1109689":{"pageid":1120438,"ns":120,"title":"Item:Q1109689","lastrevid":66451116,"modified":"2026-04-12T10:09:55Z","type":"item","id":"Q1109689","labels":{"en":{"language":"en","value":"A polynomial-time solution to Papadimitriou and Steiglitz's ``traps''"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070663"}},"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":"Q1109689$6E1D82FB-7F50-4B6D-A7F0-8064CB62C2F8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30b19d99195b5aa9fd7fe610b75dc683904dc404","datavalue":{"value":{"text":"A polynomial-time solution to Papadimitriou and Steiglitz's ``traps''","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109689$5D024FBC-4DB4-40DC-8B44-A2E8A46019AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dfa68891ed10a774521f3a3ef561352f11ceca5c","datavalue":{"value":"0655.90085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$84DBDAC2-66E7-46A8-87C3-46F711C58C12","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eee169fe57de48fd72afbcbf9d4305295b49ba71","datavalue":{"value":"10.1016/0167-6377(88)90077-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$BCC4B2A1-7E18-4BA8-8265-4F8E12B6F2E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2f742cd818e373159c2b3dd23e882e382fe7ad1","datavalue":{"value":{"entity-type":"item","numeric-id":286986,"id":"Q286986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$F9996E9C-B79F-48E2-BEE8-834E88064B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afb20ad30ffa52e0802e4180df09a4ca34fccf7f","datavalue":{"value":{"entity-type":"item","numeric-id":189591,"id":"Q189591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$1CE9468D-4FB8-4D50-B3AC-D84CCA338706","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$47CB6D62-950C-4052-871B-E9918E314B27","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1109689$9136E91D-C2C1-48F1-A447-225A88DEF13D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7175a89603df88aab429d66ad9ec33fda0f644e","datavalue":{"value":"\\textit{C. H. Papadimitriou} and \\textit{K. Steiglitz} [Oper. Res. 26, 434-443 (1978; Zbl 0383.90105)] constructed a class of instances called ``traps'' for the symmetric travelling salesman problem with \\(n=8k\\) cities. The instances in this class have exponentially many suboptimal solutions with arbitrary large weight, which are much different from the unique optimum solution, and thus the local search algorithms are ineffective to solve the class of instances.    In this paper the authors show that this class of instances can be solved in polynomial time by linear programming relaxation appended with k subtour elimination constraints.    Section 1 describes the class of instances given by Papadimitriou and Steiglitz, and states the properties of the instances; Section 2 gives the linear programming formulation of instances; in Section 3 the authors prove that the class of instances can be solved in polynomial time by linear programming relaxation appended with k subtour elimination constraints. Hence these instances are not traps to this algorithm based on linear programming. Finally the authors conclude that the algorithms based on linear programming for combinatorial optimization problems are substantially different from algorithms based on `local search' or `exchange' arguments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$68E7D641-EE13-478E-BB40-5B54662AC06E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$DBDDB637-9DB0-4204-B6B0-17F674F0711B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$6552A98B-075D-4853-A577-12183651AE68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$81F2B9C8-3830-48BD-BFDA-0387FDB743D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$405245A6-E95B-40AE-B0FD-4DEF8374ABD0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f3b7a15895c21e2f2ba7a88522e229919afc196","datavalue":{"value":"4070663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$4C046B90-0934-4CEE-B205-742A4E08E443","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$FF103E21-65B7-4A60-8C76-35682C4D4870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6165801d7b82a2ed40c0b9cdceaa9e284ad9587","datavalue":{"value":"traps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$EF09DAB1-4100-44B7-BA58-B75A5229B426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa7cd0d6eb57488f805762963d96d7600df3bccf","datavalue":{"value":"symmetric travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$F28C6F15-2AFB-4353-A02E-FBA13911B0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$29BD0590-B221-4AD5-8D62-E8D2CD2A9548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5b952c797fc461956f3a97882477e8ab79d1512","datavalue":{"value":"linear programming relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$CAA6310A-B975-44AC-BED4-60F3221CB174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39bef4794d648ae828e0eab4fa40446081f4fff","datavalue":{"value":"subtour elimination constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$1B49C1C3-EC43-4091-AB77-F4948A0EDEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1ff5a5e657abc0a392084b74b3342d23f2f4c9","datavalue":{"value":"local search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109689$F724E13C-8912-449B-A877-61CB6106773D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f8851f7d7ed4147f596ab1e98283df373347f7d6","datavalue":{"value":{"entity-type":"item","numeric-id":180312,"id":"Q180312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$A2BFA77E-DD3C-49BB-9B1E-9316A0000EB2","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":"Q1109689$550ACAC3-75A6-4842-ADF6-50FDD9A7C259","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70c08afbe6574f1ceee49b06bb908a08b4646a24","datavalue":{"value":"https://doi.org/10.1016/0167-6377(88)90077-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109689$A187C785-5479-4281-A560-A99A2D2B7498","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5d2126557e1db2596829155acee1e6c0c2d24e4","datavalue":{"value":"W2020813360","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109689$694B0851-3A6F-48F2-8063-7E4BE8163187","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2e34f2d00f3ab616b227145acdba74c6bec5ae","datavalue":{"value":{"entity-type":"item","numeric-id":5378825,"id":"Q5378825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$1B234A18-1922-4CA6-8F08-07AFC31A893F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8bced2c88bb3f79c405b650dcc49d42df378140","datavalue":{"value":{"entity-type":"item","numeric-id":3696859,"id":"Q3696859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$CBC4199F-CC5D-405A-A9EA-156F71A66175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9cdc996ad6a2d6bc6c15f31d7c4c57ae7effab5","datavalue":{"value":{"entity-type":"item","numeric-id":3888840,"id":"Q3888840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$00110448-EDF2-44F6-8F4F-562848125E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07cea2adf94240fba0126a6368a864b03ef99c18","datavalue":{"value":{"entity-type":"item","numeric-id":5378843,"id":"Q5378843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$30C4FC45-4775-459C-A21B-5E94658137CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde83dc2358b044be23eaeb3226ac019d5e33e09","datavalue":{"value":{"entity-type":"item","numeric-id":5378639,"id":"Q5378639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$B62334EB-13CA-4597-8F28-AD3480A55C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c893b7b17db5da0cf71bed489830282949b84","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$75AC6532-DBCD-407D-A2C6-07E7FAAB7EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4960d97c11c0cd0f282650fb582b7cd310577033","datavalue":{"value":{"entity-type":"item","numeric-id":3256638,"id":"Q3256638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$A4CAF1E7-7E89-4B4D-82E8-040476A0C759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ec3551e542a2037cd2ac977ae6f5126640f32c5","datavalue":{"value":{"entity-type":"item","numeric-id":3875699,"id":"Q3875699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$FA4B8347-D88D-462F-8E71-44C2D66C5B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4acdec91b79be04d2fc5ae4414cedb0f10d4d3f","datavalue":{"value":{"entity-type":"item","numeric-id":1821798,"id":"Q1821798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$E9D40832-29EE-4FCE-8348-0D72E5BC0DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32866bf2d31b9cf1002630f1a4c01f322b0cc4f7","datavalue":{"value":{"entity-type":"item","numeric-id":3217947,"id":"Q3217947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$4C796455-33D7-4D04-A0D9-E07F1EA018EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"863d85a27692194b44f3937e4bf5bab9e65d3396","datavalue":{"value":{"entity-type":"item","numeric-id":3714900,"id":"Q3714900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$B474EE64-DABA-4E68-86CD-6F194F729CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2d7941d0b26099a80a70765368bbd5212826ec8","datavalue":{"value":{"entity-type":"item","numeric-id":3677509,"id":"Q3677509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$ABCAF36E-5A9C-46BD-A38D-23C4BE02CD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c85ad1c11b4c2c66512da23bc9ecc32c36b4a62","datavalue":{"value":{"entity-type":"item","numeric-id":5510390,"id":"Q5510390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$0C4534DF-53BA-4F13-8199-54F6E9AF2F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0930d57b126d4670b8351b41154baa4cb1f96e2","datavalue":{"value":{"entity-type":"item","numeric-id":5671788,"id":"Q5671788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$CDEC7AB9-D18B-4689-B365-69E9E08B02B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aceb20a0099a6a99996d28208b1583727eba126","datavalue":{"value":{"entity-type":"item","numeric-id":3875701,"id":"Q3875701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$400BA8CA-815D-4A19-81AE-F6B2346FD5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c5769e6e6a35ae57b366b486d7b893a8167041d","datavalue":{"value":{"entity-type":"item","numeric-id":1089267,"id":"Q1089267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$9A8C1740-043C-4D00-B9AE-65BC66343F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$28DB0F08-C4A7-421C-9641-16D99C7D01FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5090218963f7454eb65bbbfc3a5878c945557f","datavalue":{"value":{"entity-type":"item","numeric-id":4162995,"id":"Q4162995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$C860FA56-8C22-4EF8-BDE3-74E351016D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6470a2d2017e1dec05e95ebc3d7cbd28334b43a4","datavalue":{"value":{"entity-type":"item","numeric-id":4723573,"id":"Q4723573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109689$582362D5-D1B3-4AAB-8450-57588D83D0A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a33ca11e4ec8c041212b4bcba19445dc9709f2e","datavalue":{"value":{"entity-type":"item","numeric-id":810369,"id":"Q810369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5d9af76a6735bfa91d921fd71953573ea1d6fa9","datavalue":{"value":{"amount":"+0.8334522","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":"Q1109689$53937416-D850-429B-AD3B-E1FCB8D8E553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35d13fbc4dbedbea1b646a98d50d2da6b58095ab","datavalue":{"value":{"entity-type":"item","numeric-id":3347631,"id":"Q3347631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"024a6da2493ba72541b290dee13a161f754ae4f7","datavalue":{"value":{"amount":"+0.81425196","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":"Q1109689$AFEE3896-185D-4CFB-8C97-F2E1FC400DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41f95096257138d4364f59f107dfcde18ca95825","datavalue":{"value":{"entity-type":"item","numeric-id":1584821,"id":"Q1584821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c844f6e8c4e395a337dd9ad788b9a7d6ece5e415","datavalue":{"value":{"amount":"+0.81420434","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":"Q1109689$D40C89B8-4B7F-45B1-9A97-20F2E88A03FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6e0eb09ffbc31b0bc70fb6b6a420a86c510bed6","datavalue":{"value":{"entity-type":"item","numeric-id":5378843,"id":"Q5378843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f51a52f4cb31afa2b6f3bf45697ec55a6761947a","datavalue":{"value":{"amount":"+0.81045705","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":"Q1109689$75291EFF-1D41-4DDD-85C0-0C4364A37895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd2e8bc3abafa647613efe7e1be185d0cb99a930","datavalue":{"value":{"entity-type":"item","numeric-id":1002076,"id":"Q1002076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86b90bd61256b5eab5584d5fdcb90f55b9a124a9","datavalue":{"value":{"amount":"+0.8102917","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":"Q1109689$3B3134B9-6955-4162-A06F-A197117C4A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1454546fe918402ab736c2573f679546f15836ca","datavalue":{"value":{"entity-type":"item","numeric-id":5297404,"id":"Q5297404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"662e3fe650ccafb1d71c3b66e7f2b9bf5d1ef5e1","datavalue":{"value":{"amount":"+0.8087471","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":"Q1109689$1E880184-627D-4BA1-86A1-DB0A314DE05B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"689d5cb272cf31f3c0970a5a769fe83af8cc8298","datavalue":{"value":{"entity-type":"item","numeric-id":876681,"id":"Q876681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd8564345b25e63e250e594f7a7e45d9c05d86f6","datavalue":{"value":{"amount":"+0.8028829","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":"Q1109689$3D9A883E-ABB1-481A-81A8-3BC08676F49D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92fe3ab8877bab36658096f1ed1290ef3d804cd3","datavalue":{"value":{"entity-type":"item","numeric-id":5450918,"id":"Q5450918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52530da0656a42099e6a6b3706dcbe333f34b13b","datavalue":{"value":{"amount":"+0.80053556","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":"Q1109689$948B9433-31A7-44D9-B22C-DF8143E62FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa852700eb1ccc58962dcd3ab44f8d452e82bb5c","datavalue":{"value":{"entity-type":"item","numeric-id":1126862,"id":"Q1126862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb86903315385068a852eff99910e51c986a5da","datavalue":{"value":{"amount":"+0.8000994","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":"Q1109689$AF6568A9-196C-494E-BE85-27D9209F64A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d3308d16a7adaa812efee5027fa4b5702524230","datavalue":{"value":{"entity-type":"item","numeric-id":2654962,"id":"Q2654962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49aa77c4067d1cc7c42ec7226cf8cd511b1da3dc","datavalue":{"value":{"amount":"+0.79919034","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":"Q1109689$16952BB6-7CBB-41BC-9D6E-A3828B3288A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial-time solution to Papadimitriou and Steiglitz's ``traps''","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial-time_solution_to_Papadimitriou_and_Steiglitz%27s_%60%60traps%27%27"}}}}}