file.pdf (406.34 kB)
All-Norms and All-Lp-Norms Approximation Algorithms
journal contribution
posted on 1996-09-01, 00:00 authored by Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat TangwongsanIn 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 Lp-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.