{"entities":{"Q4978037":{"pageid":7007616,"ns":120,"title":"Item:Q4978037","lastrevid":58387863,"modified":"2026-04-05T00:14:29Z","type":"item","id":"Q4978037","labels":{"en":{"language":"en","value":"Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6761869"}},"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":"Q4978037$2A682BCD-CFFA-4AC0-8138-4AAC92036C6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"594750037be4c1de0d8da1e86bdf5e4e464ba781","datavalue":{"value":{"text":"Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4978037$81C53571-93E6-48FD-8329-B95B887B2B2B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"30aa03f7602075c505c42243860aef2e1c1f946b","datavalue":{"value":"1370.68110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$F9F590C1-A84A-4D83-8AB8-9CF58C89A340","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef5f48a23438819553078435a494d2d431505656","datavalue":{"value":"10.1145/3055399.3055412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$C770A81A-98E6-4243-9C0F-B1AF53582D8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18a901d1a78f32110e38e24a7f49a346af16da30","datavalue":{"value":{"entity-type":"item","numeric-id":513281,"id":"Q513281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4978037$72B32BFD-10AD-4E9B-8A57-9015583C544A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df0e235d1b1d733bcc53fdadfc8ec0d6b69c89be","datavalue":{"value":{"time":"+2017-08-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":"Q4978037$4EE615B5-CD03-4A37-B6E5-503CB751153F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"636306d0276b66a005aeabc1012a22592f14660c","datavalue":{"value":"https://arxiv.org/abs/1611.05991","type":"string"},"datatype":"url"},"type":"statement","id":"Q4978037$F1CB5279-850B-4403-9114-67E9B98F8275","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$01CEDA3A-5897-4E38-9762-A27525750FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$84FCF3BD-F177-417D-BDA9-8F2C404ABE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$6E1B78D8-309D-4533-8C0D-05A1CDEE76A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$D9D32C85-34F6-44A8-93EC-9C9F0C803E66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c2969667056204c1a57c58be349be2db9f7b5574","datavalue":{"value":"6761869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$281D4F99-110D-4198-99BD-B8BABCE5B619","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2d5d5c6631c3449598b2306bfdc6ffc0df98dfb","datavalue":{"value":"densest \\(k\\)-subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978037$11776A42-4A52-46CC-8A96-91BEA1628926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978037$29015891-5641-42D8-8C52-C4A7CA784978","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":"Q4978037$B4BF39CC-C680-46E0-ADCA-67FF30C775ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"81881ea9b27b850a1ce89ead195199ce56e1ac79","datavalue":{"value":"W2552383377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978037$03E71E0A-638B-4567-A446-BE47A3E95439","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0279325c5e9c5731a27c2bae84beb5eb998df91d","datavalue":{"value":{"entity-type":"item","numeric-id":5271715,"id":"Q5271715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4978037$492081CC-E9F8-4CDF-A212-6B0E32B8679F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22809bdb5b201d201624fd1a09cbfb7413f33bce","datavalue":{"value":{"entity-type":"item","numeric-id":4575829,"id":"Q4575829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc395f68795f000042cb221e75d4ddaca9cddb5e","datavalue":{"value":{"amount":"+0.9173733","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":"Q4978037$DDDD9B2A-79D8-4447-B90C-032F235FBDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3320132e66da0c03d3cdd824621f9ece207756fc","datavalue":{"value":{"entity-type":"item","numeric-id":4914440,"id":"Q4914440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"335490e07d0e20ca39b54b68de60451ae2fc067a","datavalue":{"value":{"amount":"+0.90968144","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":"Q4978037$CBBB42FC-750B-4922-95C0-C99CE5901929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"758251c33e2d2c2ac7b598a0492f78f85976aabd","datavalue":{"value":{"entity-type":"item","numeric-id":1683124,"id":"Q1683124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15e50e68cb459045f0d4d41f81042597c0e9b38b","datavalue":{"value":{"amount":"+0.90512955","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":"Q4978037$08BCA257-F358-4872-A507-0B3AB3F857FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3101e0955827583b4b8064bffd3cad063140071","datavalue":{"value":{"entity-type":"item","numeric-id":2427738,"id":"Q2427738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"244a1a8acda6ee248ed1a1651d4d9fa75a6f8fe2","datavalue":{"value":{"amount":"+0.9003662","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":"Q4978037$ED0CCDAE-45FF-444D-9663-62FC093D00CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcb0da61d4d7f494aa1adbc12ae2d58c41407172","datavalue":{"value":{"entity-type":"item","numeric-id":2334039,"id":"Q2334039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3080f710d4f27b221cdb81f5aad930083ac917f","datavalue":{"value":{"amount":"+0.89507854","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":"Q4978037$2F839A76-D0CF-4131-B5A0-CFD5A5C6F823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5e7182d65706603baa4ceb026ac249ee6bd63c5","datavalue":{"value":{"entity-type":"item","numeric-id":3174693,"id":"Q3174693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5b7d1993a8eff38edab9e0302a6a7f5798af7d2","datavalue":{"value":{"amount":"+0.8867845","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":"Q4978037$9D09E323-FAB1-40BE-8174-873CFDA3C7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4678d95d8a8717946919d6597dd3f03bf83326ba","datavalue":{"value":{"entity-type":"item","numeric-id":4636436,"id":"Q4636436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aab9cd861de5c22b90e7841e10d6ff80245a397d","datavalue":{"value":{"amount":"+0.8867844","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":"Q4978037$8450D59F-C59C-4E12-96CD-81273B018B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9051f8d131b30e99c8b4c6823e67614fd4abc75","datavalue":{"value":{"entity-type":"item","numeric-id":1810886,"id":"Q1810886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad8218a7c51cc1efc1b38d18110ba2c96503a39d","datavalue":{"value":{"amount":"+0.8856733","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":"Q4978037$404E6A34-8292-4CB3-B621-8358CC7E64A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4ae3552da2a0e706cf6d8a3924cae464f17ff7c","datavalue":{"value":{"entity-type":"item","numeric-id":1776068,"id":"Q1776068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e6c85103e589b4647ee28c4c192e8a38901cf21","datavalue":{"value":{"amount":"+0.88486314","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":"Q4978037$8A389F17-6195-49E7-ADD3-520060EC4A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de5e12c50d96adfee33b3260e13bcb922ea88915","datavalue":{"value":{"entity-type":"item","numeric-id":5930156,"id":"Q5930156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c94ffa7d083ee5a1d8c6726810002e0411b172cc","datavalue":{"value":{"amount":"+0.88412946","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":"Q4978037$D836A57E-68C9-42A9-9CAA-A05E75B31DBA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4978037","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4978037"}}}}}