file.pdf (406.34 kB)
Download file

All-Norms and All-Lp-Norms Approximation Algorithms

Download (406.34 kB)
journal contribution
posted on 01.09.1996, 00:00 by Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat Tangwongsan
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 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.

History

Publisher Statement

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Date

01/09/1996