Before revision:   UnitMaxQP, where A \in \{-1,0,1\}^{n\times n}, admits an (1/ 3d )-approximation in O(n ^{1.5 when the corresponding graph has no isolated vertices and at most dn edges. -
After revision:  UnitMaxQP, where A \in \{-1,0,1\}^{n\times n}, admits an (1/ 3d )-approximation in O(n ) time when the corresponding graph has no isolated vertices and at most dn edges. -