Before revision:  We suggest the first provable PTAS algorithms for these problems that compute (1+ epsilon )-approximation  in time O(n \log (n) /epsilon^2) for any given epsilon \in (0, 1), and constant integers k, d , t \geq 1, including support for streaming and distributed input.
After revision:  We suggest the first provable PTAS algorithms for these problems that compute (1+ \epsilon )-approximation in time O(n \log (n) /epsilon^2) for any given epsilon \in (0, 1), and constant integers k, d , t \geq 1, including support for streaming and distributed input.