{"entities":{"Q634686":{"pageid":636534,"ns":120,"title":"Item:Q634686","lastrevid":63140535,"modified":"2026-04-11T10:52:02Z","type":"item","id":"Q634686","labels":{"en":{"language":"en","value":"Improved approximation algorithms for label cover problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5939454"}},"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":"Q634686$FF4CBE2F-9B4F-4ECA-BF12-88D6084CC496","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"655b484ac6c2f655e4f5ebaf8797a2529b45f915","datavalue":{"value":{"text":"Improved approximation algorithms for label cover problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q634686$5D8E9C6F-0A66-481C-A933-C7B2075163A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a1227da6af2bb0594682872e89df6f4f441abb86","datavalue":{"value":"1218.68197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$668D406E-146B-49A2-8C46-FEF3559E43CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b91a0993eed4b97259d696eb647afd9b20aa4c0e","datavalue":{"value":{"entity-type":"item","numeric-id":634685,"id":"Q634685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$5042E6A0-0D85-4150-980A-F93F04E9640F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3098471736f417aa552d69c3165075e7ba3a336f","datavalue":{"value":{"entity-type":"item","numeric-id":487271,"id":"Q487271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$926F91B1-960F-49BA-AE8C-CA1162F278E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad2e86f5f3dec5ee08f5279d9401b2d10e41bcfa","datavalue":{"value":{"entity-type":"item","numeric-id":1117702,"id":"Q1117702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$E70D4E6A-384A-40CD-85D1-8A0526B12E9B","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":"Q634686$2DF7FCB4-C3B7-4258-BA83-23FF803DCCE0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e46a6b83be9fcbd5764c46af6454b5ea03b3b70d","datavalue":{"value":{"time":"+2011-08-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q634686$7B69E362-E6BE-48DD-BDC5-A6F30EBF9DD6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$B5681027-9056-4CF2-96F3-A106085344F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$3B51909C-6C03-489A-AEEF-57F2BFEA0E32","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"320fae727eea8c7e4335973c08d62a69bb4a60cf","datavalue":{"value":"5939454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$0B346E63-8FAE-43D7-9947-5FC83A0480FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e490dcaadbc686a94d0085a10ea46e6faccdf26e","datavalue":{"value":"\\textsc{Label Cover}","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$91E0DF23-2318-43CC-A49A-C231F2734E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$8F69539D-4B4F-4E67-8A7F-92CB6C597DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$72BB219B-A4C3-4C27-9B43-C4020240C35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a180e8f6923716c9457731144643deb2e7d7a76c","datavalue":{"value":"\\textsc{Min Rep}","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$92718D59-1DB1-4FB5-91B1-0C35AFD4B658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae1cb6c90eb79f4adefd1dd38984dae7f1aee0d0","datavalue":{"value":"\\textsc{Max Rep}","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$BAD1A951-2ADC-4FD5-8DA3-3C2FDA595D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5622a63faa3ef23e6a4f496d880712f5042ee4e","datavalue":{"value":"\\textsc{Densest \\(k\\)-Subgraph}","type":"string"},"datatype":"string"},"type":"statement","id":"Q634686$2C059429-2CD8-4514-9884-8EF96C331A57","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":"Q634686$32C8E2DF-ED17-4A1C-8F72-A38CBD09D230","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e78e4fa97ae00489792d9acd4a717a5cbd425434","datavalue":{"value":"https://doi.org/10.1007/s00453-010-9464-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q634686$C24D16BC-8437-4B55-9723-8693A7DDD9DF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1ae441ae6be0dee4dc310646709b80724b32769c","datavalue":{"value":"W2108967854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$FD4E2C74-88C6-4398-BA42-FD2BBEE2D72B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8a5a268659c4baf9f470d35179b3045a9e7c64c","datavalue":{"value":{"entity-type":"item","numeric-id":5901420,"id":"Q5901420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$A79BDDA9-EF3A-4088-834C-9ECA1F382001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"702f0afed0ff12acec467dc949a7a6178a30a71a","datavalue":{"value":{"entity-type":"item","numeric-id":1356888,"id":"Q1356888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$D4148B0A-DE2C-475B-B067-DF8C8F939850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9c5b7bd3d8caab92d214aab256aced43c1dff9b","datavalue":{"value":{"entity-type":"item","numeric-id":2875146,"id":"Q2875146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$34944E80-6796-48FF-86C1-5ACE347E8FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1fd0cfc30d420400a60fabd0b240d27d17657f3","datavalue":{"value":{"entity-type":"item","numeric-id":4633906,"id":"Q4633906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$488C50D9-9FB0-4ACD-AAE6-81B30CEAF718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f587970ac194a2aa883b8d83741c7148c690325","datavalue":{"value":{"entity-type":"item","numeric-id":5233698,"id":"Q5233698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$91FFA77F-B1EF-4432-B971-3BF0AD1B8CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f96c75437da094476a83da9bcb96e67a5c02ae3","datavalue":{"value":{"entity-type":"item","numeric-id":3579502,"id":"Q3579502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$53199D48-857C-4FB4-8708-2E20808A99A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cf97a2601d7f318015e8196af2231723669d634","datavalue":{"value":{"entity-type":"item","numeric-id":2819606,"id":"Q2819606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$488F2DE1-D331-4065-A954-E5E8C689DD3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a796034671f1d07728ab79c68e82e75fec096b1a","datavalue":{"value":{"entity-type":"item","numeric-id":2754183,"id":"Q2754183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$A68C6F9C-A715-4A17-91A1-E811DE5B95EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9a9d189eab91c569087f4bcba4c1bdc4535d51c","datavalue":{"value":{"entity-type":"item","numeric-id":2464336,"id":"Q2464336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$2CC921F4-5B95-487C-8DFE-B73F14BDBD4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21871374a0259cd2e1124b08cc2c58c20fad6720","datavalue":{"value":{"entity-type":"item","numeric-id":2944490,"id":"Q2944490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$9D3F3627-A036-40D7-8A63-22E28F94FB16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9255f79487c588cbfa51c8d070056aee32ac52","datavalue":{"value":{"entity-type":"item","numeric-id":3603461,"id":"Q3603461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$AAE73515-5032-4521-BA35-29C40A7B52DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe21462215c697993c2b7db5afc53aef75a74835","datavalue":{"value":{"entity-type":"item","numeric-id":877193,"id":"Q877193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$A8837C04-D740-4C12-9A48-A366852C49E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b58968a0c1deafa65a49fe085b615bddb97e960","datavalue":{"value":{"entity-type":"item","numeric-id":5897767,"id":"Q5897767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$CB32DB8A-540B-4C77-9AB2-EBE4E286FE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24470a0a944fbaf9ee6181fbc49b02a7037f9ed6","datavalue":{"value":{"entity-type":"item","numeric-id":5757457,"id":"Q5757457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$4286EA5C-6DBA-4DD0-9459-1F3E580BA99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d5ee5049d3877545a0f1957ab82266b215c4a0f","datavalue":{"value":{"entity-type":"item","numeric-id":5945922,"id":"Q5945922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$62397BFC-0BBB-4A62-92C5-8DDA477A870D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ea6b9fbb293ae0077cfce35426980e21d16a51","datavalue":{"value":{"entity-type":"item","numeric-id":4651489,"id":"Q4651489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$94CB56C0-5789-4E93-8A91-B065D1D867C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"595d81a95e7a958032a9b972dc60fb6ab036823b","datavalue":{"value":{"entity-type":"item","numeric-id":924541,"id":"Q924541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$109E54D6-4373-4F67-A5F7-7ABD736D79B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc3a9d225f35a297c93d7c3ca15b93e5452085e","datavalue":{"value":{"entity-type":"item","numeric-id":853685,"id":"Q853685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q634686$C09A38DB-01EE-48CA-9FC1-63B9701C054E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"56c89e82fedbfd386a7a89ea828a199cf6fc1317","datavalue":{"value":"10.1007/S00453-010-9464-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q634686$38231BA9-491B-4672-920A-49A806666607","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1bdede1133c9e0d8da497ae3db9d3dfac1e6ff9","datavalue":{"value":{"entity-type":"item","numeric-id":3639232,"id":"Q3639232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba421e87ba5b469ff5dabfdcfa8f0a199aa73387","datavalue":{"value":{"amount":"+0.9945816397666932","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":"Q634686$29822638-C0D6-43AF-B94C-D18AA38A9B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2c94f72ed60f50af9e473bf5126ed037084f8b1","datavalue":{"value":{"entity-type":"item","numeric-id":4575796,"id":"Q4575796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dec0caf66ecee51c385a247b056d6c8491d9fe4a","datavalue":{"value":{"amount":"+0.8429481387138367","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":"Q634686$2D71423D-0907-4299-B785-1F9BA8FD7E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5703f310fac0feb83fa9cd17be991b9655dcc172","datavalue":{"value":{"entity-type":"item","numeric-id":3075522,"id":"Q3075522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa51b72ac7873a45784ac5a8f0e4aa689be2a3cb","datavalue":{"value":{"amount":"+0.8350474238395691","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":"Q634686$C7C8E049-3D02-47B2-959F-6625904E2C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"161f5f3c10a0b04741ba7d5aa4a1057a718dbcb2","datavalue":{"value":{"entity-type":"item","numeric-id":1029090,"id":"Q1029090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e2fb34e6216a504a3cbf06540530c56925b962e","datavalue":{"value":{"amount":"+0.8326079249382019","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":"Q634686$101F9939-D321-4824-881B-A612AD06F6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae68a06dfa6b8868c71eece957c7bfa24b28d0f7","datavalue":{"value":{"entity-type":"item","numeric-id":924541,"id":"Q924541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19c9e40ed5460a117ced15539cf68213df1654cd","datavalue":{"value":{"amount":"+0.7916449308395386","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":"Q634686$20A8BD22-FA0C-4379-ABCD-34D0560A6733","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved approximation algorithms for label cover problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_approximation_algorithms_for_label_cover_problems"}}}}}