Before revision:  We resolve these questions in the affirmative . More specifically, our contribution is two-fold : 1. In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time : an O(\alpha)-approximation in linear time.
After revision:  We resolve these questions in the affirmative , and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms : 1. In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time : an O(\alpha)-approximation in linear time.