All-Norms and All-L_p-Norms Approximation Algorithms

In many optimization problems, a solution can be viewed as ascribing a “cost” to each client and the goal is to optimize some aggregation of the per-client costs. We often optimize some L_p-norm (or some other symmetric convex function or norm) of the vector of costs—though different applications may suggest different norms to use. Ideally, we could obtain a solution that optimized several norms simultaneously.