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. - MaxQP admits a (1-\varepsilon)-approximation in O(n  ) time when the corresponding graph has bounded local treewidth . - UnitMaxQP admits a (1-\varepsilon)-approximation in O(n ^2 ) time when the corresponding graph is H-minor-free .
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 is d-degenerate. - UnitMaxQP admits a (1-\varepsilon)-approximation in O(n ) time when the corresponding graph has bounded local treewidth . - UnitMaxQP admits a (1-\varepsilon)-approximation in O(n ^2 ) time when the corresponding graph is H-minor-free .