Not only a PTAS is known for this problem.

It is also possible to compute a PTAS, even without seeing the entire adjacency matrix !


In 2011, Ailon [has showed][1] that by a smart choice of queries you can compute a $(1+\epsilon)$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) of the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.


  [1]: http://arxiv-web3.library.cornell.edu/pdf/1011.0108v3.pdf