Difference between revisions of "Open Problems:39"
(Created page with "{{Header |title=Approximating Maximum Matching Size |source=bertinoro11 |who=Krzysztof Onak }} Consider graphs with maximum degree bounded by $d$. It is possible to approximat...") |
m |
||
| Line 6: | Line 6: | ||
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}}. | 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}}. | ||
| − | ''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? |
Revision as of 03:19, 17 November 2012
| 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?
