{"entities":{"Q3053148":{"pageid":3063864,"ns":120,"title":"Item:Q3053148","lastrevid":51118685,"modified":"2026-01-16T18:55:01Z","type":"item","id":"Q3053148","labels":{"en":{"language":"en","value":"\\(O(\\sqrt{\\log n})\\) approximation to sparsest cut in \\(\\tilde{O}(n^2)\\) time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5810166"}},"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":"Q3053148$7AC9A9E4-B2E0-4DCC-BC21-9A3F2BBB6B1D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2cab32ed4cfe1c8b5b1fb89b7408c9dedfa171a5","datavalue":{"value":{"text":"$O(\\sqrt{\\logn})$ Approximation to SPARSEST CUT in $\\tilde{O}(n^2)$ Time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3053148$EE0D3092-EE1B-4E5B-AA5B-7C85817540DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"29d918ab8a1f1a624c29e238e8e5abe9b17bf522","datavalue":{"value":"1207.68441","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3053148$58207728-F6BD-4961-A6C6-8304164810EC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ce1356d802bf8e6ea67eb6afebbba5115f73afe","datavalue":{"value":"10.1137/080731049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3053148$D9B798F0-7689-4B33-A0A6-7DE011AC2961","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"11634f81649135e9b4758fbbf94b85ba9d546570","datavalue":{"value":{"entity-type":"item","numeric-id":304245,"id":"Q304245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3053148$F59FC3D1-15B6-4A89-BE84-A2AF03EB74D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d6137d878d3d0c1a6e5ecd88b72e34b91c5e968","datavalue":{"value":{"entity-type":"item","numeric-id":1009220,"id":"Q1009220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3053148$9E18A9F0-D7D7-4A37-B29F-9457C3F0B653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5fa856eb9cad7c56d02923351b2c4236ede2b614","datavalue":{"value":{"entity-type":"item","numeric-id":6480589,"id":"Q6480589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3053148$86DDE2A3-51D3-4A69-B8C3-E482CA130470","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3053148$779EB2CC-4976-4E11-9CBC-E7BD2B583B39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05f87c5170bfb76ad381b07fc66abe335aacd4cf","datavalue":{"value":{"time":"+2010-11-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3053148$664F7361-9FDD-410E-A123-8D5392642EE0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3053148$197211A3-486D-4FC3-889C-3226F810E853","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34249754e043227102c898abe9b39b8eda285f29","datavalue":{"value":"5810166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3053148$39B85D07-DDC5-461D-83E9-7156E91881C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q3053148$BF369AEA-4621-44ED-912C-AAFAAD9E0984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca836d0da2022f6d379c08d6baee32868167312d","datavalue":{"value":"expander flows","type":"string"},"datatype":"string"},"type":"statement","id":"Q3053148$9C07E490-657C-4AAD-BDDD-533D547C9E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3ee062addc73ba3d95ae0508e1b43a639bc7501","datavalue":{"value":"multiplicative weights","type":"string"},"datatype":"string"},"type":"statement","id":"Q3053148$58D15AAB-548E-4C47-A3A9-B42C3EF9F596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47707cecca3e9198ba8d22847129e1c614378cd6","datavalue":{"value":"sparsest cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3053148$D9C12181-90C2-46C2-8E54-B58DEBCA3AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b2f7f4d12c36f454dfd11d8484e4d5638e5506","datavalue":{"value":"balanced separator problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3053148$76755BE6-2F52-4BA3-BD27-1305E6571BDA","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":"Q3053148$9CF7D0D9-8D6D-4E4D-9DE1-E592CA98372A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e0b67f40500b0d67b558865f9527dc87c039c54d","datavalue":{"value":"https://doi.org/10.1137/080731049","type":"string"},"datatype":"url"},"type":"statement","id":"Q3053148$A03A5D32-0D7A-40E6-9789-792951AE6F12","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce12a735e54ca07634ad1a21a30d846f1fb44eb9","datavalue":{"value":"W2103444054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3053148$EC93FF40-80F1-4B3C-AD8A-87D07A1EC759","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d6edb8936970fb7bd9941fef1d9963e6ae95c1","datavalue":{"value":{"entity-type":"item","numeric-id":5899510,"id":"Q5899510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"947c18eff068389335e5fd892df906fde983c93c","datavalue":{"value":{"amount":"+0.8713970184326172","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":"Q3053148$F8F1B71E-4ECB-4DE0-AE3A-54BFDCB7E16F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4f6048724da9708f932f8847c1e75bf838b49fd","datavalue":{"value":{"entity-type":"item","numeric-id":5899507,"id":"Q5899507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c12f02d6c75436456d59c1d5db89fe7804b10d4a","datavalue":{"value":{"amount":"+0.8712918162345886","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":"Q3053148$84A8C088-5B72-41D5-9A32-94FC62E6726C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ec5a7d0872c4e695b021160c8a005d48dcfab7e","datavalue":{"value":{"entity-type":"item","numeric-id":5891927,"id":"Q5891927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c5a918cb0e0a62f2f1ebbdec1358dd649d71baa","datavalue":{"value":{"amount":"+0.8691815733909607","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":"Q3053148$5AA8EEC3-6D3E-47F0-8988-5197C6831044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f9020a2c0e82560463792d0c2b0fc87ea03604a","datavalue":{"value":{"entity-type":"item","numeric-id":5901073,"id":"Q5901073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2688269b5c9a7ff847276e02a260c3870405c304","datavalue":{"value":{"amount":"+0.8646084070205688","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":"Q3053148$37082E30-9980-4AE5-9B7B-0F1C19D32D94","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":"6f802af3618c453d8dd380254b8b083383b51b47","datavalue":{"value":{"amount":"+0.8433964848518372","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":"Q3053148$57B45C8B-D7B9-40C5-AC27-E83B348A6879","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3053148","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3053148"}}}}}