https://sublinear.info/api.php?action=feedcontributions&feedformat=atom&user=Soben 2026-06-07T19:48:48Z User contributions MediaWiki 1.31.10 https://sublinear.info/index.php?title=Open_Problems:39&diff=1376 2023-09-30T01:45:04Z

<p>Soben: </p> <hr /> <div>{{Header<br /> |source=bertinoro11<br /> |who=Krzysztof Onak<br /> }}<br /> Consider graphs with maximum degree bounded by $d$. It is possible to approximate the size of the maximum matching up to an additive $\epsilon n$ in time that is a function of only $\epsilon$ and $d$ {{cite|NguyenO-08|YoshidaYI-09}}. The fastest currently known algorithm runs in $d^{O(1/\epsilon^2)}$ time {{cite|YoshidaYI-09}}.<br /> <br /> '''Question:''' Is there an algorithm that runs in $\operatorname{poly}(d/\epsilon)$ time?<br /> <br /> == Update ==<br /> Behnezhad, Roghani, and Rubinstein (FOCS 2023) showed that $d^{\Omega(1/\epsilon)}$ time is needed for this problem, therefore negatively resolving the open problem above.</div>

Soben