{"entities":{"Q765522":{"pageid":767371,"ns":120,"title":"Item:Q765522","lastrevid":51436322,"modified":"2026-01-18T05:46:50Z","type":"item","id":"Q765522","labels":{"en":{"language":"en","value":"There is no EPTAS for two-dimensional knapsack"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6016062"}},"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":"Q765522$61939E7C-E813-4C36-98C5-90D49BE8E9AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c00edc0fdeadceeeb14d06342856821b979a5c87","datavalue":{"value":{"text":"There is no EPTAS for two-dimensional knapsack","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q765522$B02DC669-71C4-4037-B6BE-53DD4751B550","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8bea2643891d47b437cc2890a07e46dae185eb0","datavalue":{"value":"1234.68153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$2A283036-70E9-4241-B9A7-A7B278C63C64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74af2766c774240a9a51b99f493075518fd0be6e","datavalue":{"value":{"entity-type":"item","numeric-id":655415,"id":"Q655415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$532446E3-1306-4C04-B15B-41D133CA05F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b451a2ac0f2c963f77b6135a280741037892792c","datavalue":{"value":{"entity-type":"item","numeric-id":313813,"id":"Q313813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$856E924D-5AB5-447B-801F-5D335BAD0D44","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$8000C09C-494A-489E-B98E-FA5B522D480A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e3a09f4fda9fcd4791a88e88ca245a42392f6906","datavalue":{"value":{"time":"+2012-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q765522$440F3A18-BA81-4766-AB32-5FE38604914B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$CD918E8A-7F6B-4087-8FDD-B6ED2AFC908E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$2273B3B1-2EF2-439C-A599-76269DE9DD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$07317982-75ED-4515-A3E2-0E56383ACE1D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c861c5ed8a1bc8b3778fd2dbbf87f7e52b736440","datavalue":{"value":"6016062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$D7B8D755-EEFE-473E-9900-9B24DB4B4E56","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"577e13ad92dbdc1b218913f0396bab8ff3c16b94","datavalue":{"value":"two-dimensional knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q765522$2E02135B-B4DC-4F90-ADCC-BED88DAFFBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f7832a48e1c4cdc6b25454bff3e1ed8beb41fbc","datavalue":{"value":"efficient polynomial-time approximation schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q765522$19DE5D5B-845F-42CF-BC03-FCC87FC1145E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q765522$A8FD3470-7380-48C2-9245-8772DE8B69E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a02b4e020864e91f8b46070c7c982fa2878da3","datavalue":{"value":"theory of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q765522$2A11D703-5C64-40A0-BE1B-13F2025BDC92","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"be21fea0a72ab925eb346981091af9198118f013","datavalue":{"value":"Q56050295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$BBF66219-177D-4043-A026-56CDDD886986","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c999c1a7fc9dbe817177ebd058dccb9f0956e5fe","datavalue":{"value":{"entity-type":"item","numeric-id":16891,"id":"Q16891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$72BE053C-56E3-49A7-B98D-D093BB25570E","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":"Q765522$2CB9A928-D907-4351-B158-B680AD3884DC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ed6673b1288c66789e3637f3acd8883c87ea53e","datavalue":{"value":"https://doi.org/10.1016/j.ipl.2010.05.031","type":"string"},"datatype":"url"},"type":"statement","id":"Q765522$8080943F-7B23-4EEB-8603-9A9831DFE08F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6220cf96b0103e8894a249e02e8774561a49bc52","datavalue":{"value":"W2067088693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$3E67A5B6-1DBD-4A3A-B88A-847267EFE8FA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7640c30cc38fbffa71e5661be9033f0cef0d41dd","datavalue":{"value":{"entity-type":"item","numeric-id":1569936,"id":"Q1569936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$E9827B28-DDB1-4D54-8F44-DBAEAFFA2FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"822d76f64bb65aa3f7f263af272aadc045be88be","datavalue":{"value":{"entity-type":"item","numeric-id":3580971,"id":"Q3580971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$B844C8F2-7D96-4A11-95E4-E7A74E0823C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$04BA6219-E034-4762-B758-9C634E70C7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"500bfeba9231a071c9bfde5b167ca0a56cfc8d2f","datavalue":{"value":{"entity-type":"item","numeric-id":673779,"id":"Q673779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$BADCB06F-3FAB-42E2-894B-24A8D6223496","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$3A6D361A-D779-441C-8CE0-EF17AECE1E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d873eb220f9c7b9bab911767ca34bf21b911b7c8","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$42BCC2A4-B2BB-4E9C-8449-F7622811FA9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89737476846006649ef2e6d7db8390636ed69c75","datavalue":{"value":{"entity-type":"item","numeric-id":3898034,"id":"Q3898034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$21308FF9-08ED-4116-B45A-3CB8F0CDDF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$EBA0BBAC-C630-4806-BB63-3D1C7B808581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fb32aee089b4d2b6b4416d3d32d0ad1726958e","datavalue":{"value":{"entity-type":"item","numeric-id":4633878,"id":"Q4633878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$99CED30A-4C40-43B4-9C8B-11C5D27BFA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aead8c01c8945fd60386818d8b15d5b1b5818dc5","datavalue":{"value":{"entity-type":"item","numeric-id":1304384,"id":"Q1304384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$C7C95FB1-D28D-481F-A45F-0C64C26B082D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6112d56aaa2ddb40728a9eaafa95b7bad68abccc","datavalue":{"value":{"entity-type":"item","numeric-id":1768594,"id":"Q1768594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$F1BC2C46-B86E-431D-911F-2D00663FF8F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"997010fa0fe64c5416cb73d2fbd5d4d0e35de9ba","datavalue":{"value":{"entity-type":"item","numeric-id":4821303,"id":"Q4821303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$DBA63F01-F1E7-4DD8-896C-E57FDE9F83EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57ea5b7a5d9b75c21c16cc766f465086f639c2e5","datavalue":{"value":{"entity-type":"item","numeric-id":3320130,"id":"Q3320130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$190C6C95-DA94-496B-813B-D4E5A4436F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc458311982cd3ce607df203c39661e390d2366d","datavalue":{"value":{"entity-type":"item","numeric-id":3718485,"id":"Q3718485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$8DC0CDB1-AD60-412A-B2C0-A791235A68E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$28A73115-A514-4061-881A-E82A63986E22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20d09513baf32113955ba3ecf79c8e2d6ab34f2","datavalue":{"value":{"entity-type":"item","numeric-id":3512428,"id":"Q3512428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765522$97F7C119-2CF5-4571-9013-AAE582A4D159","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"a273afc4122762711c938bec157f858f19150783","datavalue":{"value":"journals/ipl/KulikS10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$5B260C41-F080-4913-B4EE-80C71F064954","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d72154b04deb08736a3b8c747446816d77e6038","datavalue":{"value":"10.1016/J.IPL.2010.05.031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765522$17A4A0A2-52DE-415D-B3A5-5DD041FEFE56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c53d747f9aaa5456c4aa6a14531f263a549f6374","datavalue":{"value":{"entity-type":"item","numeric-id":4575740,"id":"Q4575740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"669e8d3f676e4c37bd4c04cb37e818750edccafe","datavalue":{"value":{"amount":"+0.8468514084815979","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":"Q765522$8D94FCCD-B616-4D25-B696-DB25F369D0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cee68c2b7d21814d13edda31392ae65ac8508bba","datavalue":{"value":{"entity-type":"item","numeric-id":4973043,"id":"Q4973043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e5f85109beaeb2edcaaa143f054be166e44821e","datavalue":{"value":{"amount":"+0.8467952013015747","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":"Q765522$8D4FEEBB-D8F4-4A7C-AC8C-BBA61B35BBE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a479e4ed2e63b8bd9a788ed9e5c65745519e27f1","datavalue":{"value":{"entity-type":"item","numeric-id":2117618,"id":"Q2117618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d87e55526efdd7f7367f1810dde70700cac4da1","datavalue":{"value":{"amount":"+0.8039169311523438","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":"Q765522$C68D7F3E-1FF8-4FF1-8A7D-CC3E16B627AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07151cb637cacfbe5c79d2901befb0c74ef27ef5","datavalue":{"value":{"entity-type":"item","numeric-id":293152,"id":"Q293152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf6666dcd8a7387ddd84bacff893763dec2c541d","datavalue":{"value":{"amount":"+0.8020772337913513","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":"Q765522$DC3F3C0B-35C7-439E-BB38-E752083FB2AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edacdef887ab8639c0a0e3d5a1cd64e3249a25b4","datavalue":{"value":{"entity-type":"item","numeric-id":5970810,"id":"Q5970810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfbaec6463f40d53ce3de53e1289834a857514c1","datavalue":{"value":{"amount":"+0.7959710359573364","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":"Q765522$EC90FB59-E013-44A1-8CD8-DE64199AAE9F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:765522","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:765522"}}}}}