Difference between revisions of "Open Problems:39"
m |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=bertinoro11 | |source=bertinoro11 | ||
|who=Krzysztof Onak | |who=Krzysztof Onak | ||
| Line 7: | Line 6: | ||
'''Question:''' Is there an algorithm that runs in $\operatorname{poly}(d/\epsilon)$ time? | '''Question:''' Is there an algorithm that runs in $\operatorname{poly}(d/\epsilon)$ time? | ||
| + | |||
| + | == Update == | ||
| + | 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. | ||
Latest revision as of 01:45, 30 September 2023
| Suggested by | Krzysztof Onak |
|---|---|
| Source | Bertinoro 2011 |
| Short link | https://sublinear.info/39 |
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$ [NguyenO-08,YoshidaYI-09]. The fastest currently known algorithm runs in $d^{O(1/\epsilon^2)}$ time [YoshidaYI-09].
Question: Is there an algorithm that runs in $\operatorname{poly}(d/\epsilon)$ time?
Update
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.
