Difference between revisions of "Open Problems:39"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m
(updated header)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Approximating Maximum Matching Size
 
 
|source=bertinoro11
 
|source=bertinoro11
 
|who=Krzysztof Onak
 
|who=Krzysztof Onak

Revision as of 01:53, 7 March 2013

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?