{"entities":{"Q689105":{"pageid":690954,"ns":120,"title":"Item:Q689105","lastrevid":63497100,"modified":"2026-04-11T13:33:53Z","type":"item","id":"Q689105","labels":{"en":{"language":"en","value":"Geometric Knapsack problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440023"}},"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":"Q689105$3C2A16A9-0417-47B6-B885-007EA60A6CFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c876495fdf378208bb05b330d8b88dbc4ae98742","datavalue":{"value":{"text":"Geometric Knapsack problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q689105$41FDFE0E-56A7-4AAF-80A6-ED15D521518F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba039618252aa24f4fd38efa67f2f1e5a9320377","datavalue":{"value":"0781.68109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689105$E8C6B5FF-B54B-486B-82E4-9D1405572ECF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae49649027d9d4fea0071d0f3fe82ff468dafd3e","datavalue":{"value":"10.1007/BF01769706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689105$F9F76825-E315-41E4-B34D-5BB36E184C1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0f96198222aeec1a9630a1398f93a76816f149d","datavalue":{"value":{"entity-type":"item","numeric-id":233538,"id":"Q233538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$B43F6D79-B96C-4E2F-835A-9BF8C414FF7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f496316b317a1071c5b5dfba5a175583d61d254d","datavalue":{"value":{"entity-type":"item","numeric-id":194031,"id":"Q194031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$AEA89392-C786-4F59-BAB6-D6E8B742C611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58051942065352f1019453b7eb1d17c25a542cb8","datavalue":{"value":{"entity-type":"item","numeric-id":244519,"id":"Q244519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$346D8322-5807-46AD-8605-BA9979997066","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":"Q689105$C4428960-55A4-4C29-92D9-20B4BDAADAAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ece7c460c78874e314a441f2bb630645a5e7532","datavalue":{"value":{"time":"+1994-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q689105$8AFA02A5-30FC-453C-B565-D42DD7BD9093","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bda81a39cbc3c19c993bb8bf7f8ce7e92a3db99b","datavalue":{"value":"We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following ``fence enclosure'' problem: Given a set \\(S\\) of \\(n\\) points in the plane with values \\(v_ i\\geq 0\\), we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the ``value'' of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, and give the following results:   (1) We show that when the values \\(v_ i\\) are unrestricted in sign, the minimum-length enclosure problem is \\(NP\\)-hard.   (2) We show that when there is an upper bound on the perimeter or the area of the allowed enclosure, then the problem of enclosing a maximum- value subset of points with values \\(v_ i>0\\) is \\(NP\\)-hard. We provide a pseudo-polynomial algorithm for the case in which all the values \\(v_ i\\) are integral. This also allows us to solve the following: Find the smallest perimeter (or area) polygon that encloses \\(k\\) points of a set of \\(n\\) points \\(S\\). Our solutions requires time \\(O(kn^ 3)\\) and space \\(O(kn^ 2)\\).   (3) If \\(v_ i>0\\) and there is no bound on the length of fence available but there is a cost \\(c>0\\) per unit length of fence, we solve various versions of the optimal single \\((M=1)\\) enclosure problem in polynomial time. The objective function that we are to maximize is defined as the sum of the values of the objects enclosed minus the cost of the fence.   (a) For the case of enclosing \\(n\\) points, we give an \\(O(n^ 3)\\) times algorithm.   (b) For the case in which \\(S\\) is a set of simple polygonal objects, and objects have to be either entirely included or entirely excluded, we give an \\(O(en^ 2)\\) algorithm, where \\(e=O(n^ 2)\\) is the size of the visibility graph of \\(S\\). If instead, we are allowed to build fences through the polygons \\(S\\), but only receive value according to the fraction of the area of an object we enclose, we obtain an \\(O(n^ 3)\\) time algorithm.   (4) We give a polynomial-time algorithm for the multiple-fence point enclosure problem, for fixed number of fences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q689105$DE7329F8-1689-4D82-A87A-0615D9F00924","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689105$D1CF068B-983E-4926-92E4-DAB19B59866A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b95d1730e150eb7424abff71ab1785752244fffb","datavalue":{"value":"440023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689105$2ED7B2E4-1E50-441D-A1CD-B82F8B699FA5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q689105$DD34765C-8189-484E-A35D-4E7BFBE4C917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5199eeda97192c23f50c511c9c4c00f1d8ebf6a9","datavalue":{"value":"fence enclosure problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q689105$1D6EFB6E-28E3-4341-9829-F09221063094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd9f81e2de676ca1bc7efadeabffd39fb5463e86","datavalue":{"value":"knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q689105$C07AEA3D-32E2-4D25-B6EE-C98B0DDA85C2","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":"Q689105$E8B060A5-8B47-4D1B-B524-76016317504F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e78add1d8b013583dbc6de9c2424cecf91acefae","datavalue":{"value":{"entity-type":"item","numeric-id":1101223,"id":"Q1101223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$A3076399-B6F2-4223-B205-3CA0FC270EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7ea44918d9cd1c3450d92ce2807e95746d9a5b2","datavalue":{"value":{"entity-type":"item","numeric-id":3833604,"id":"Q3833604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$6B7B6548-7E70-4675-B1A3-2391D06657FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c51a0463b95f55a754d0b2de6a2b6f27abf3ea4e","datavalue":{"value":{"entity-type":"item","numeric-id":3832585,"id":"Q3832585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$86FF518F-782B-4362-8EBE-400BD4696720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e7abeaf8cc88f6e630fb91975b50983535be4e1","datavalue":{"value":{"entity-type":"item","numeric-id":3221405,"id":"Q3221405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$90DBEFC7-4246-4601-B05E-9573E570FBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78500d6fcce07550315e59f9dcf0c342a2c4678","datavalue":{"value":{"entity-type":"item","numeric-id":3361924,"id":"Q3361924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$D73BA707-CC21-45D6-9C37-164C30AB6B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42c6d852be18ae77ef309660b4ddf583e7dead77","datavalue":{"value":{"entity-type":"item","numeric-id":1076347,"id":"Q1076347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$6FC19DFB-6DCD-4D23-9DBA-142E3DFC2CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3568c3d245cd3f2cf4f94e727ae0ed4c28ae6d68","datavalue":{"value":{"entity-type":"item","numeric-id":4274652,"id":"Q4274652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$D1DA9C4E-7442-4031-BC95-0D3384EB694E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$0B3F711D-1A38-4166-B418-EE765C21E52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faf457f1212ea0750678c0a874399d7e5b07f4bf","datavalue":{"value":{"entity-type":"item","numeric-id":912393,"id":"Q912393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$14232F0C-BA4F-4598-8F8D-6A28338F1ECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06bb2e50a70deee23cbf38ebcc3da4e0467bcd5e","datavalue":{"value":{"entity-type":"item","numeric-id":1186081,"id":"Q1186081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$1217FC9F-A42F-44E8-9B6E-8CE634052999","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":"Q689105$27CDCA9E-0E9E-428B-A735-96FA7C4432E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b32de81f138bfd0051adfbd8bd15bcb529446c0","datavalue":{"value":{"entity-type":"item","numeric-id":3982713,"id":"Q3982713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$E452464A-8AB0-4DF5-8192-97C9BAE049B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81078a7460abf00d8505be96a597e8d07c36cc68","datavalue":{"value":{"entity-type":"item","numeric-id":3771608,"id":"Q3771608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$C2A08D26-3F97-4148-BBFA-5347974B5F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb23bc554851f9631b7f70848303798dbbfa9ec1","datavalue":{"value":{"entity-type":"item","numeric-id":1068550,"id":"Q1068550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$59C736E4-1B3B-4719-89B4-3AFC4EA7A781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d834b2f061333007e84559a210df1dabd1b7c737","datavalue":{"value":{"entity-type":"item","numeric-id":3993418,"id":"Q3993418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$014DDC47-A459-4FF7-BB98-3B7D4DFF91E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e6b44c968e141586a82998b57f7cb6c54b47528","datavalue":{"value":{"entity-type":"item","numeric-id":3201801,"id":"Q3201801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689105$F4BCEC77-9D21-45E9-9C04-448C086C4AE3","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":"Q689105$BF540F92-5E3C-4AE0-BFC2-01E8217A9E9F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c218dc1a4760151dfa1b943b73cd3085b83bed9a","datavalue":{"value":"https://doi.org/10.1007/bf01769706","type":"string"},"datatype":"url"},"type":"statement","id":"Q689105$EEB99524-7286-41D8-B6DA-29505CAC3963","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c20acddd09b42e06bffbc9339b12ab551ee0741","datavalue":{"value":"W2061213672","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689105$464B8D40-F3A8-4CB6-B2C7-5AA4F58379D3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8804e7abb3facd231f63d8f8a49ba62ee45559a","datavalue":{"value":{"entity-type":"item","numeric-id":4037416,"id":"Q4037416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"272cd73df05aa3231cfe12d5e1ba3c202a486533","datavalue":{"value":{"amount":"+0.9999997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$B39B2350-8B3D-40FE-A9DD-13981AB27290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae2e2dff9c3a9a0d455085d9fb78100b197e6a4","datavalue":{"value":{"entity-type":"item","numeric-id":5035877,"id":"Q5035877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2a753aaaa4a9269d8740db734aeb9fd2c2b53ac","datavalue":{"value":{"amount":"+0.9128487","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$60A59F0B-DA99-48B3-94A5-470ED6CDAA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"624b6b63c673e8a3873351fbeda9df0d22c6fad6","datavalue":{"value":{"entity-type":"item","numeric-id":827125,"id":"Q827125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29fcd8102899a350a6659c62c8b02d1883171ae3","datavalue":{"value":{"amount":"+0.8908489","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$722A3FC9-837E-43C9-BD54-B69C1D75857C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff3c1665c2849adc36420ffc2e9fa5e61046b191","datavalue":{"value":{"entity-type":"item","numeric-id":2168057,"id":"Q2168057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e3956c81fc515a36a3ffd04efa371a43facc70e","datavalue":{"value":{"amount":"+0.8887019","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$329E0F39-D835-4AA8-86C1-476C213FC6CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"549b62d3b310ac8a586a5d23f6af789badb2c25a","datavalue":{"value":{"entity-type":"item","numeric-id":4247440,"id":"Q4247440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ccdc227ed05976fe1e478608f3495a8e53094d0","datavalue":{"value":{"amount":"+0.8880414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$2E9CDEDD-CEEA-4A07-AE92-5036C2B4E6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0cc247e1bb7ee2dadae39287dcf00ce3f6ea3c0","datavalue":{"value":{"entity-type":"item","numeric-id":5477436,"id":"Q5477436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3266bedd0a224e0bfb9d6803136719efbc80861","datavalue":{"value":{"amount":"+0.87939024","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$AABA685F-C3A1-43E8-B309-C5C0C06A6C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f838920e10ef94ab2d8f6e845b53db352e283861","datavalue":{"value":{"entity-type":"item","numeric-id":2359152,"id":"Q2359152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58ba7cd7e545152eb3948446b609b58beb7b35c9","datavalue":{"value":{"amount":"+0.87927544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$EA843E98-E002-441B-845E-BA4A73608C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28aa36e57874fd2a2a65c1e768c2255e086e64cb","datavalue":{"value":{"entity-type":"item","numeric-id":266044,"id":"Q266044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fcf13fe1e3a1fa7572bb7a97cee25c593c9adc3","datavalue":{"value":{"amount":"+0.8773912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$FF479FE5-30FE-4D29-89F2-F1C590500A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3887174004fd86ac6eb427143ef18056a2b8dff8","datavalue":{"value":{"entity-type":"item","numeric-id":4782747,"id":"Q4782747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"032e78c945360ba27d2fb90b90349fc9a230e372","datavalue":{"value":{"amount":"+0.8770133","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$2B852029-121E-4D86-BA84-D06300A27982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5180bd5c1e1f0e6d944985a45137712911ff8ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5363013,"id":"Q5363013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"732de8d1328f363226bb67081b7ee9a6a0bc07b0","datavalue":{"value":{"amount":"+0.87560344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689105$487E0EDF-91B5-4900-A607-CF5E1BCFDFA9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Geometric Knapsack problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Geometric_Knapsack_problems"}}}}}