{"entities":{"Q5212767":{"pageid":7242338,"ns":120,"title":"Item:Q5212767","lastrevid":58478529,"modified":"2026-04-05T09:46:19Z","type":"item","id":"Q5212767","labels":{"en":{"language":"en","value":"\\(O(\\log^2 k/\\log\\log k)\\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7160506"}},"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":"Q5212767$5559634C-38D8-48B7-9B7F-DDDC7F18B908","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2de74bcd68a19b0509cfcbec1e385bdb251c4d5f","datavalue":{"value":{"text":"<i>O</i>             (log             <sup>2</sup>             <i>k</i>             / log log             <i>k</i>             )-approximation algorithm for directed Steiner tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5212767$C851D61B-F910-4E30-9F48-D44C037A43C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"277751586aa681747d87fbef930be01be77c5102","datavalue":{"value":"1433.68614","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$CD0F4A69-9406-42BF-96FE-28B96084F739","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa02201d1b264ddd85f6a43f8dfe41994d8be789","datavalue":{"value":"10.1145/3313276.3316349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$78398CA8-70DC-4E29-9162-051FE102EEAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"56e992a1ebab66e67a2ab1e823ea360dfebc6857","datavalue":{"value":{"entity-type":"item","numeric-id":334925,"id":"Q334925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5212767$2BBDE518-418C-4081-8D1D-40A484F3F7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"433e640f4acbffdd1fef3f2b4ef3fe5a14204f1f","datavalue":{"value":{"entity-type":"item","numeric-id":487014,"id":"Q487014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5212767$9090058D-AA51-48E6-8C3F-A20D885129C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7995cb68cf0d1cc7c1fa01508b0ed49ea12604c","datavalue":{"value":{"entity-type":"item","numeric-id":1718127,"id":"Q1718127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5212767$06780142-03BB-4CC2-8984-099D7C653C92","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7ec30071785b97eb964fee27a72d549b6933f168","datavalue":{"value":{"entity-type":"item","numeric-id":5212741,"id":"Q5212741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5212767$1409D8E2-DEAC-448D-A52B-46077C5A154F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9d2fff2838771d2e0e512e8ba6e71ab0bdd7329b","datavalue":{"value":{"time":"+2020-01-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5212767$4B26BBE6-A9FA-409B-8B02-6FB5CF8EF2EC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f5904f3bf56e964562e55cb564ad3e5d759b0b15","datavalue":{"value":"https://arxiv.org/abs/1811.03020","type":"string"},"datatype":"url"},"type":"statement","id":"Q5212767$645691B0-8F83-4EC7-BD1C-2C7B4DDEEA23","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$03B72F1D-30BD-45EA-A834-1B4CE119F190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$FD280760-6530-474E-B595-3410C9D80D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$A5BE2B7F-D9DC-4434-B6A7-57372C61F960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$DC8D7F76-D2D7-4847-97B9-45CE4145FE1D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7eb968673fdf61a9e59e548a713ed20cce0ac5a7","datavalue":{"value":"7160506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$2477B429-EB51-4F93-8733-B457B1CD25DF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fc97a188365db788bf14e8eec2f83b206cae86b","datavalue":{"value":"directed Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5212767$09468279-58DF-4FAD-BE6A-B257E9DB2064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46f6fff5db24a271c6a21f5ac988fa0847c79382","datavalue":{"value":"quasi-polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q5212767$5C1AC2BE-5B2E-4EF7-86CC-7A5C2ED4E722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8708943551101484429a99030d17e4c4a89f3ce7","datavalue":{"value":"Sherali-Adams hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5212767$7B683951-6F9E-4DFD-B46E-76758C533F35","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":"Q5212767$16DF29EB-5E37-487A-8596-D24ED579E568","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c8a4385aa0d43041bde69fddc60f582771eec8f1","datavalue":{"value":"W2900307033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5212767$F8984D5C-C80B-434A-9BE7-CFFF480701C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0561965e7c2de42c7f46204a81fb498bd9a795ee","datavalue":{"value":{"entity-type":"item","numeric-id":5890148,"id":"Q5890148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0238557b7aba04f6b8ed88674417b31399a6b6c","datavalue":{"value":{"amount":"+0.955724835395813","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":"Q5212767$B81B45E4-6F6C-42AD-85A3-E67D43B6E842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64120b90725c3b4840214c87df77659b089f1c2e","datavalue":{"value":{"entity-type":"item","numeric-id":4598214,"id":"Q4598214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5e7be07d3602897c0ced33fa658ade887dfda01","datavalue":{"value":{"amount":"+0.8527606725692749","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":"Q5212767$507D6F22-45F2-49F6-9784-E5B97DCDC10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc13bc4644c40a0fd7d58d16bc241839251ff668","datavalue":{"value":{"entity-type":"item","numeric-id":4250182,"id":"Q4250182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2112d3661897a181bfe48cba8b493a4b329040a6","datavalue":{"value":{"amount":"+0.8375418782234192","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":"Q5212767$D75E8420-57AE-4762-B353-192EFDFD169D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9fa56107e248e17d7181adc6863a06de25f4043","datavalue":{"value":{"entity-type":"item","numeric-id":4828915,"id":"Q4828915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0528046957f19975a3756b173da323eda9d72345","datavalue":{"value":{"amount":"+0.8369412422180176","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":"Q5212767$BEA89AEA-BC4C-4BE0-9B78-4D63B0792CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1eef229de4c723bac20519ea4ed67b652b4f21b","datavalue":{"value":{"entity-type":"item","numeric-id":4939606,"id":"Q4939606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3adbe84138c449aa3feecf79e19d830ddbfd3be5","datavalue":{"value":{"amount":"+0.8347464799880981","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":"Q5212767$272FFF11-93A5-418E-B1A3-A4638DC9CAF1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5212767","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5212767"}}}}}