Before revision:  We describe a O(n^{k-1} \log^{d-k+2} n)-time randomized (1+\varepsilon)-approximation algorithm for this problem with d and \varepsilon constant.
After revision:  We describe a O(n^{k-1} \log^{d-k+2} n)-time randomized (1+\varepsilon)-approximation algorithm for this problem with \(d\) and \(\varepsilon\) constant.