{"entities":{"Q1126838":{"pageid":1137587,"ns":120,"title":"Item:Q1126838","lastrevid":66188319,"modified":"2026-04-12T08:08:26Z","type":"item","id":"Q1126838","labels":{"en":{"language":"en","value":"On approximating NP-hard optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1184382"}},"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":"Q1126838$3EA79504-B99C-4B8C-B4FD-6B8B5085FA72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8936496065700cb7813853e72558475f54407a4","datavalue":{"value":{"text":"On approximating NP-hard optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1126838$1C45CA1D-AE4C-4B20-ADFE-EBE2914BEF27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"729d9a4a92992f1dce0deb5fc6c5300174cd3388","datavalue":{"value":"0910.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126838$B4A987EB-23B9-4758-B369-F28FE57A2486","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4add3c5163a5eee9bbe20dc8a36386ab43b68fd6","datavalue":{"value":{"entity-type":"item","numeric-id":168490,"id":"Q168490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126838$232F347C-48AA-4A97-A7D2-8D7E6C0B9928","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0213be50779ba5bffb4613228959545da04beaec","datavalue":{"value":{"time":"+1998-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1126838$E6C58A29-57AC-4518-AE0F-92ED8AFB5072","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36139b44f8acd6acd758f302c274ff6ea4d9cdd9","datavalue":{"value":"http://www.emis.de/journals/DMJDMV/xvol-icm/14/Hastad.MAN.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126838$9DFC54EC-F44E-44AE-BABA-EC1BEA22E006","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"527cdd7d456ff15168e65e4b26735f70d1cd247d","datavalue":{"value":"Consider the problem of satisfying the maximal number of equations in an over-determined system of linear equations. The author shows that it is NP-hard to approximate this problem within a factor smaller than 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126838$568BCA74-A2FA-416E-9267-7B193053D0E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126838$6291198B-29C8-44FE-A687-84BAF90A743D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126838$03F6BC67-AE27-46E4-AACC-931E415AADDC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"738a9181599ab33df2acef38c3b03f55166457db","datavalue":{"value":"1184382","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126838$1606F558-EC18-4DA7-85B4-0C374CDC5BC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bf370b13ef323414748928003bcc0535e335d6c","datavalue":{"value":"NP-hard optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126838$FB127A02-DCEB-4D92-BDE9-D4E55FF900E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"935f36f1a01b7e2997f780d23942b95b18a4551b","datavalue":{"value":"approximating algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126838$9558C0FA-9D23-4595-ACFD-E65A4085275A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58ac6701bff6972da991c5209d8dad72896f4570","datavalue":{"value":"linear equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126838$1CCFE82B-2B3C-4C3A-994D-7A1FA3126783","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9023554ef09c8d4f4813676b620b15e4c22a0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1083474,"id":"Q1083474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126838$C5B9CA56-A41B-423D-8018-59F43C551288","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":"Q1126838$68FADEEC-D29C-40AF-8252-575E654CC486","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"734de8a4801f326298229557e893bc83148c423e","datavalue":{"value":"bafkreianocwv56jjl2x4xoxq4zxqxw6vjs7fqsas3wv7ejvebjjmremlfy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126838$8BC1A2F0-24B8-49EA-860F-A3E3A8932621","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b65112490151e1e3e734b769178083d8b70adf","datavalue":{"value":{"entity-type":"item","numeric-id":1045886,"id":"Q1045886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b06f1e15f27a23127c25a0e81b4a69499a2890c7","datavalue":{"value":{"amount":"+0.8092015981674194","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":"Q1126838$B0984EA4-0D99-4F31-94FC-B2CACE1C17D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dfef4dc959c4897026c29743a9b898ec6273efa","datavalue":{"value":{"entity-type":"item","numeric-id":3680277,"id":"Q3680277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94f5c3c36f9101ece3d929e524dce874039ca386","datavalue":{"value":{"amount":"+0.8013716340065002","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":"Q1126838$D0DFE4B1-E9CE-4109-8B90-A5ED90ED8025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c024e3d6465d22d803661e388b1198abb76789c0","datavalue":{"value":{"entity-type":"item","numeric-id":4549232,"id":"Q4549232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f858c494a4a56a5fb4a791a36ce1c72918ba7d6","datavalue":{"value":{"amount":"+0.7936616539955139","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":"Q1126838$2859E1E9-C10A-45A9-AD10-9B0E0C822A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3725349e7e31477b444ec07da5c3f0f2ce6f4d01","datavalue":{"value":{"entity-type":"item","numeric-id":5054856,"id":"Q5054856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4380eb6f5096710bbb86b4d78a4965832b08c8f0","datavalue":{"value":{"amount":"+0.7866680026054382","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":"Q1126838$CEB20A0A-5FB2-4C45-876E-C7C6BB079004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91180eda8f021b1a5a7116dcf1d980fd22e7f02f","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48530c4d244da6c3db2090dd29773aef86408fdf","datavalue":{"value":{"amount":"+0.7822509407997131","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":"Q1126838$96EF73AA-FA67-4B13-8CE1-7CEA5615994B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On approximating NP-hard optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_approximating_NP-hard_optimization_problems"}}}}}