{"entities":{"Q1588908":{"pageid":1599648,"ns":120,"title":"Item:Q1588908","lastrevid":47545168,"modified":"2026-01-02T01:11:01Z","type":"item","id":"Q1588908","labels":{"en":{"language":"en","value":"Clique is hard to approximate within \\(n^{1-\\epsilon}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1541202"}},"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":"Q1588908$EF3D48DA-086A-43B6-B1F3-4C5DABCC4AA9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"936478dd8f2f1bf1f4d7b39f6b39a557d37d3d03","datavalue":{"value":{"text":"Clique is hard to approximate within \\(n^{1-\\epsilon}\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1588908$854F07FB-C671-48CA-941A-B366A484EC81","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69e8e05aa1ec744b32d4533575a59c2482c12c41","datavalue":{"value":"0989.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1588908$02BE7AEA-E182-455F-B567-7C9DCDEF1C7A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1d37677925a6ef8fd51578c33b502846c32f101f","datavalue":{"value":"10.1007/BF02392825","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1588908$2C982B57-AA38-4016-9EB5-A394E061FA90","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"09f456a274e455e5e5b05b055e42e0cbb108679d","datavalue":{"value":{"entity-type":"item","numeric-id":163102,"id":"Q163102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$0BF8F9F4-0765-45BE-B168-341E3DA71741","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"990752c320d29232b9e0b8025fa1f119d1be577c","datavalue":{"value":{"time":"+2000-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1588908$2A6FD914-55B6-4839-B488-DCF00D4DF79F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34ff26234e628d7e9a3a756f09f4c8ce6986f095","datavalue":{"value":"The author of the paper studies the possible performance of a polynomial-time approximation algorithm for the optimization version of the CLIQUE problem, traditionally denoted Max-Clique, which given a graph \\(G\\) and an integer \\(k\\) tries to identify whether there are \\(k\\) nodes all of which are connected in graph \\(G\\). The author strengthens the results of Bellare, Goldreich and Sudan who proved that, for any \\(\\varepsilon> 0\\), Max-Clique cannot be efficiently approximated within \\(n^{1/3-\\varepsilon}\\), to prove that, for any \\(\\varepsilon> 0\\), Max-Clique cannot be efficiently approximated within \\(n^{1-\\varepsilon}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1588908$E06FE218-0AD3-4DB9-838B-4DB38F33E12C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69b93dc27d4387ede14176674c0b1d85f1013e20","datavalue":{"value":{"entity-type":"item","numeric-id":587098,"id":"Q587098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$697925D5-8DB7-4866-918B-5ED1B76BE41C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1588908$D5C8A82C-ECA0-45A4-9122-FA10EB4A72D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10091d7b822faa8079cf39ae26e89798269ff137","datavalue":{"value":"1541202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1588908$AD206D8C-5292-4979-83C3-F569011A9A5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b6d7fc79c7172c20189a84d73f93acf5eac931f","datavalue":{"value":"CLIQUE problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1588908$17E26A3D-2E95-4576-9A86-60723CEF73FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f19186e40f528b02e566ced18ccbd94ea79d6e2","datavalue":{"value":"Max-Clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1588908$6EC27FDE-26BE-418B-802E-F7C7B7B2B834","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":"Q1588908$6CB137E9-5F6F-44E9-9F39-3976A2C124FD","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":"Q1588908$7101750D-E454-4550-9124-767104ADAC38","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6dcd39aec2caf2e1f7c762c2328413f12f8d6ac0","datavalue":{"value":"Q56210419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1588908$087C7C3D-94E3-4EA8-8F0D-C33F17E5F4C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$C9415082-85FF-4D22-BF18-6F2A7B5D8427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f3a5a6ef5b4dad2d6e7e841bea784191d0a73c","datavalue":{"value":{"entity-type":"item","numeric-id":3841041,"id":"Q3841041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$D87A3A1C-AC83-438C-9A18-F7C33697F65D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5321cf483aab0fa6bee08b9510a1c268bf22de20","datavalue":{"value":{"entity-type":"item","numeric-id":685724,"id":"Q685724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$BB95C283-BE4C-4892-B939-0C6DE97D0105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f659facd2c123b7904cc0ad05cce16026166bb3","datavalue":{"value":{"entity-type":"item","numeric-id":3129465,"id":"Q3129465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$669C0E50-3C0F-4871-890C-7A2A350D0D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8452767e48792d351acf5067c416d60a7b2b74","datavalue":{"value":{"entity-type":"item","numeric-id":4388899,"id":"Q4388899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$FDADB8A7-DDB6-4D7F-80E1-C95C05D7D990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"127ecfb8af7bef406c624e706903bb6e0473005e","datavalue":{"value":{"entity-type":"item","numeric-id":5248498,"id":"Q5248498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$7835789A-29D9-4022-94B9-4054CE6105E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80b805c507f6d8a7d93762d55b2650a00aa20f8a","datavalue":{"value":{"entity-type":"item","numeric-id":2817610,"id":"Q2817610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$C31D7CF9-CCE1-40C5-B90D-AEFFE1961396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d065c583efdebca15b3be81cfc1ee4103b8d3a5","datavalue":{"value":{"entity-type":"item","numeric-id":1184733,"id":"Q1184733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$2D8C6E81-F33F-4D75-8396-20F6C6D4B480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c6592a49761f461763cc72d2b91dee964ad0498","datavalue":{"value":{"entity-type":"item","numeric-id":1196452,"id":"Q1196452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$2DAA1C02-1EEB-4951-9121-D72C6B009270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f87faac27c8a301e13d9dc1f37095f0bc22d084c","datavalue":{"value":{"entity-type":"item","numeric-id":4228484,"id":"Q4228484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$A6787821-4662-4FA1-BCCB-0EDAFE7580A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e4ec3391671959471e0dda3a6f5f980abca5fa","datavalue":{"value":{"entity-type":"item","numeric-id":4371671,"id":"Q4371671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$973473EB-D885-42F1-A9C4-AA559B6A0DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d370efbfaa4b23bb97276694fd664243539ac2ec","datavalue":{"value":{"entity-type":"item","numeric-id":4507353,"id":"Q4507353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$507A11BA-9A18-47D9-A180-420BBCE09FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dfd00192dd30d513c242d1d547e159907bf8620","datavalue":{"value":{"entity-type":"item","numeric-id":1341733,"id":"Q1341733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$1673FD66-92B2-45AA-A7CF-788C7CDC9267","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":"Q1588908$73CA7176-7D5F-4F5C-AADF-70ADC2E2AC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd7366be4fb014e19a626ef8e0bbfe54e4dc7a91","datavalue":{"value":{"entity-type":"item","numeric-id":2817633,"id":"Q2817633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$62EB3056-A34E-42B9-80C5-B36BC4923D5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae477ba2300400eec2908d55329cb4248dc074d4","datavalue":{"value":{"entity-type":"item","numeric-id":3833627,"id":"Q3833627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$92DC6E18-4630-4533-BFE8-5DE8CD2A4987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3780c823bc7cba4ab77d9843affed6857f5700e3","datavalue":{"value":{"entity-type":"item","numeric-id":4228449,"id":"Q4228449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$6F63C6B7-E957-45C0-AC15-FD429B1D7F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4f6417af3313b2a4f1959b9dee0bb7940ea475","datavalue":{"value":{"entity-type":"item","numeric-id":4526964,"id":"Q4526964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$949880D3-737A-47AA-AB52-528757B75ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$F5C456EC-478E-4524-B9F5-26F63394A484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37ddc25bc6ddeb4fef28927db93d392a886040f2","datavalue":{"value":{"entity-type":"item","numeric-id":4302792,"id":"Q4302792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$0BE7E3EA-39D7-4A41-83D8-017EB36830BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$3AAB51CB-9FE0-499B-B3E5-391888A252DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$5D6F0D76-96EC-48C1-AACE-F548ECE1412C","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":"Q1588908$DF70A2CB-1C46-4321-838C-4B71E6E862CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7c1b8cc24016a7c6b464cd2135f72b919e9781","datavalue":{"value":{"entity-type":"item","numeric-id":4388898,"id":"Q4388898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$2BEC2B1E-AC20-4CCC-8BFD-91FF13E008DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d268b2809bbcd70c788c93a5e38330e04b05334","datavalue":{"value":{"entity-type":"item","numeric-id":4302793,"id":"Q4302793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$F6B54B45-E95E-4CFB-830C-7C4685367F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c0cb7a161ad919041f584212aa203008053bea","datavalue":{"value":{"entity-type":"item","numeric-id":5691296,"id":"Q5691296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1588908$3E98A995-E0B6-406F-B415-38B3FCC8A53C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc53058464638c90e3bf537a4778da6031859c71","datavalue":{"value":{"entity-type":"item","numeric-id":2754129,"id":"Q2754129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b3a89e0a19dd745c38ee2baac38a0a5ae9f92bb","datavalue":{"value":{"amount":"+0.901458978652954","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":"Q1588908$B09D9FAA-C249-4610-9687-A5EC8710026D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27354edb5bf0bbb0ac053d60faffa3f9ba88f2d5","datavalue":{"value":{"entity-type":"item","numeric-id":1877696,"id":"Q1877696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9241618d19dc95eb3966421d7bf2ad9706c324d3","datavalue":{"value":{"amount":"+0.8387075662612915","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":"Q1588908$A0D0C681-1D10-478E-9490-EFB8B98B92A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fec0c16cb1d1aef64a14b9dae1cc3ea69ae3f802","datavalue":{"value":{"entity-type":"item","numeric-id":4286115,"id":"Q4286115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1923f740b7ff121dcc977fd655c31426e9e0aefd","datavalue":{"value":{"amount":"+0.8265747427940369","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":"Q1588908$6C89B876-3B5E-42D3-9EEA-0F0C001E342C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b6689ff328685ceba87cbc888dcbb84d1a48d88","datavalue":{"value":{"entity-type":"item","numeric-id":1183423,"id":"Q1183423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00421081457e8c41ee3b69b49c439c56e0c7b83a","datavalue":{"value":{"amount":"+0.8260272741317749","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":"Q1588908$BFBB9DDD-C8C8-4C96-BFA0-96EDE1D6A17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70eb67847c50998c578ef2592c6186d2f43dc9fa","datavalue":{"value":{"entity-type":"item","numeric-id":4652632,"id":"Q4652632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"585910b6bccb9629db51045be3b7159a160466a7","datavalue":{"value":{"amount":"+0.8245426416397095","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":"Q1588908$B7351595-D8C8-4726-BE92-0D5A22214DFC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1588908","badges":[]}}}}}