Before revision:  We complement our hardness results by providing approximation schemes for computing \lambda_\infty and the spread constant of star graphs, and investigate constant approximability for weighted trees. Finally{\em   , we provide improved approximation results for the maximum variance embedding problem for general graphs, by replacing the optimal orthogonal projection (PCA) with a randomized projection approach .
After revision:  We conclude this case by providing a fully polynomial time approximation scheme. We further study a generalization of spread constant in machine learning literature, namely the{\em , we provide improved approximation results for the maximum variance embedding problem for general graphs, by replacing the optimal orthogonal projection (PCA) with a randomized projection approach .