{"entities":{"Q7361693":{"pageid":31520618,"ns":120,"title":"Item:Q7361693","lastrevid":105367277,"modified":"2026-10-07T13:36:46Z","type":"item","id":"Q7361693","labels":{"en":{"language":"en","value":"Verified Approximation Algorithms"}},"descriptions":{"en":{"language":"en","value":"AFP entry Approximation_Algorithms"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed37db3e0bc7a2adce717f8d230cbd5baf938dae","datavalue":{"value":"https://isa-afp.org/entries/Approximation_Algorithms.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361693$13670A3C-D953-4023-9540-9A5A43FA2A1B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e7dda9f513b34510b8ef72a410fb933e4f2cfc48","datavalue":{"value":{"time":"+2020-01-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":"Q7361693$0313EF45-3E21-45C9-B63B-D0C930AF6770","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"4a25b2a8eb23972ceedaed437a1377c31f70a279","datavalue":{"value":"Robin E\u00dfmann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361693$73D72D61-A818-4439-A983-FCF9B34B07A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361693$079F9CE6-F602-441F-B29B-75C8070471D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3f884915338caf208cded30117221a3ea888b4d7","datavalue":{"value":"Simon Robillard","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361693$311C292F-364A-4D87-963F-1FFBE3B9F2F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"6bac2c615bc1887b213917daf57c64a498114fad","datavalue":{"value":"Ujkan Sulejmani","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361693$EFB5BFE4-4004-4E1F-8C7F-F9F1D04D3330","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff12789c0e4ada378c390a2717e35e014ae611f5","datavalue":{"value":{"text":"Verified Approximation Algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361693$9064B8BA-6B45-47CB-B4F4-3B3BCAA2FFE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7d22ef455e0d646a01849757cf71b4ba1054140","datavalue":{"value":"We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, set cover, independent set, center selection, load balancing, and bin packing. The proofs correct incompletenesses in existing proofs and improve the approximation ratio in one case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361693$6862DDD0-4957-4AFF-B177-A4F16720DD36","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f94d3df904ea2ca8efbcc93ac1fe6b3e0fe90bd","datavalue":{"value":{"entity-type":"item","numeric-id":5713947,"id":"Q5713947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$F90E712B-0666-4C60-8EFF-DCEBFFF347C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7fa632cca2a52feb40e231e5ab9541063399a2d","datavalue":{"value":{"entity-type":"item","numeric-id":1400475,"id":"Q1400475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$B4F1EDE4-1A50-4D93-B533-607BD8DB01A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f977c20973258200e63609c8f0130b5e8a6e35d","datavalue":{"value":{"entity-type":"item","numeric-id":5049009,"id":"Q5049009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$DEADA0E2-1DCE-4DCF-9265-CF7E3B1D6640","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$328D1750-5356-449C-89C8-A3BFFA955DAA","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"1213e4bf209f93a0bd2b72ccadf03a45aea2311a","datavalue":{"value":{"entity-type":"item","numeric-id":7360773,"id":"Q7360773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$7838D9DE-884D-4550-B392-52ACF3687738","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361693$0DB39F7D-6459-455C-8C5F-568DA9383444","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Verified Approximation Algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Verified_Approximation_Algorithms"}}}}}