Before revision:  We present an exact algorithm solving the problem in O(n \log ^4 n) time and a (1+\varepsilon)-approximation algorithm running in O(n + 1/\varepsilon^2\cdot\log ^4 (1/\varepsilon)) time.
After revision:  We present an exact algorithm solving the problem in O(n \log ^2 n) time and a (1+\varepsilon)-approximation algorithm running in O(n + 1/\varepsilon^2\cdot\log ^4 (1/\varepsilon)) time.