Before revision:  MaxQP admits an \Omega (1/ \lg a_{\max )-approximation in O(n^{1.5} \lg a_{\max) time , where a_{\max} is the maximum absolute value in A, }  when the corresponding graph is d-degenerate . - UnitMaxQP admits a (1-\varepsilon)-approximation in O(n ^2 ) time when the corresponding graph is H-minor free . - MaxQP admits a (1-\varepsilon)-approximation in O(n  ) time when the corresponding graph and each of its minors have bounded local treewidth .
After revision:  MaxQP admits an \Omega (1/ \lg a_{\max )-approximation in O(n^{1.5} \lg a_{\max) time , where a_{\max} is the maximum absolute value in A, } when the corresponding graph has \delta n edges . - UnitMaxQP admits a (1-\varepsilon)-approximation in O(n ^2 ) time when the corresponding graph is H-minor free . - MaxQP admits a (1-\varepsilon)-approximation in O(n ) time when the corresponding graph and each of its minors have bounded local treewidth .