{"entities":{"Q4978003":{"pageid":7007582,"ns":120,"title":"Item:Q4978003","lastrevid":58386735,"modified":"2026-04-05T00:08:31Z","type":"item","id":"Q4978003","labels":{"en":{"language":"en","value":"The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of \\(\\sqrt{\\log n}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6761838"}},"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":"Q4978003$EA0EDAEB-64ED-4FE1-90D9-3CA69F7AE97F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a81bf97165da729ce22d737a66f25d68fb939a4a","datavalue":{"value":{"text":"The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of \u221alog n","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4978003$E82173D8-61BD-4E50-AFC5-3CABEB918D0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1059630c0efc94da9d83b39dbaa075dd610799fc","datavalue":{"value":"1370.68235","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$9E907ADA-5EDB-472D-861C-4E1A16C0DD00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d57a33bed81b10a73253b00f36760864e38dc59","datavalue":{"value":"10.1145/3055399.3055413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$F4A83E21-F1FC-4968-86C3-9E7DE07BDF83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e15064a955e2b0fc1477893d6cd3b38b1f1b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":185634,"id":"Q185634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4978003$BDF60E23-2B37-444C-A497-33B31697C1FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"67c29a6a6779b9db8392d6d69bd0d39bee2537fd","datavalue":{"value":{"entity-type":"item","numeric-id":282836,"id":"Q282836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4978003$F447552A-F271-4392-9BEC-29704C17B727","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":"Q4978003$63B44898-4741-4823-A208-E263630AA83D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50aef4058b7e0aef4c12646800e9142cf729298b","datavalue":{"value":"https://arxiv.org/abs/1704.01200","type":"string"},"datatype":"url"},"type":"statement","id":"Q4978003$0D28CC4F-7A16-4A22-99FD-187F6D2DF28A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$F7468578-72BE-4619-B034-A3EA5A3C7503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$50C60657-79F8-4738-BE04-3AD7AB438B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$CA65F281-6EFA-4F72-8308-D6E5361A6F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$3859CD56-4D22-49BF-A227-1C660C4433BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$940868F5-A7EA-4476-86C5-360FCB6A71F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$C9AD12AC-AD6E-4E44-AFAC-425AF3304A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$9EF0C61A-950F-48E5-B31D-946672D3C9A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65624a4588a56f06cde84ad25acbb15bf7f3c732","datavalue":{"value":"6761838","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$9F57ECBD-CAD9-402D-B94B-38F316DF0E21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47707cecca3e9198ba8d22847129e1c614378cd6","datavalue":{"value":"sparsest cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978003$5F41D876-97CD-44BB-893E-18CF04A45730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978003$F6E4F728-157C-4C1D-A774-B8F98A67B781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92422e06ef4c684021c00092323f3640686c981b","datavalue":{"value":"metric embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978003$1744190A-C34E-472A-92BD-E32B6E15E7E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0145dbb175f229104a70deaeffc1099143a20d","datavalue":{"value":"semidefinite programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q4978003$9BAA7CB8-F261-49BF-AA8F-36E485D3AEEF","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":"Q4978003$60CC6292-3120-4B02-B157-60EA178F7F58","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d8b1708b8e253d4c1f1f8e1cdb6f356876d3749d","datavalue":{"value":"W2607237413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4978003$8E1CC617-7327-4068-8F67-7CE01F822385","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":"Q4978003$5212E0AA-05E7-4139-BF9E-45169925D50C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da9597f2cc5b24e3664d74b558d41d7bb3a03e1d","datavalue":{"value":{"entity-type":"item","numeric-id":5171219,"id":"Q5171219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7841c58e6250fd4fb69024c4678456a4bd8c9cf","datavalue":{"value":{"amount":"+0.8709309697151184","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":"Q4978003$55147771-4468-444A-A1E9-E662890BCD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aebd14577fb65f70d34c36c5d3cc073581e2e83b","datavalue":{"value":{"entity-type":"item","numeric-id":1643390,"id":"Q1643390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cb2032a0ffb5a8fd0432b7a780cc28d2e348eac","datavalue":{"value":{"amount":"+0.8049587607383728","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":"Q4978003$77E65E11-FDCF-482D-9A54-BFDE343CC9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d26da7385ab8e34b06d3f984c908cf461f71ae9","datavalue":{"value":{"entity-type":"item","numeric-id":5245363,"id":"Q5245363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98e4c0723f5c4ea4446272df4a91bc800e6c4917","datavalue":{"value":{"amount":"+0.7981559634208679","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":"Q4978003$AC8D340D-6C30-4415-BD25-34CA37DB3DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f009c27c6eaf1ad6a602f81a24277b4c8c8942d","datavalue":{"value":{"entity-type":"item","numeric-id":3096660,"id":"Q3096660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9905e6ade8247f0183de2573592cf9af16e283cc","datavalue":{"value":{"amount":"+0.7617431282997131","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":"Q4978003$80B1C87D-800A-4459-BB64-D4EE6AC79B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0912f787c926d7c20d74822e00e5cca7ecc62a99","datavalue":{"value":{"entity-type":"item","numeric-id":2931416,"id":"Q2931416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21df8f2a8d6bc61a2332d94fa9d86bf7c609dacf","datavalue":{"value":{"amount":"+0.759486734867096","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":"Q4978003$9C0676E5-5B39-4E0C-AF1E-6E0C4E1C2B30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4978003","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4978003"}}}}}