For multi-criteria problems and problems with poorly characterized objective functions, it is often desirable to simultaneously approximate the optimum solution for a large class of objective functions. We consider two such classes:

• Maximizing all symmetric concave functions, and
• Minimizing all symmetric convex functions

The former corresponds to maximizing profit for a resource allocation problem (such as allocation of bandwidths in a computer network). The concavity requirement corresponds to the law of diminishing returns in economics. The latter corresponds to minimizing cost or congestion in a load balancing problem, where the congestion-cost is some convex function of the loads.

Informally, a simultaneous A-approximation for either class is a feasible solution that is within a factor A of the optimum for all functions in that class. Clearly, the structure of the feasible set and the constraints have a significant impact on the best possible A and the computational complexity of finding a solution that achieves (or nearly achieves) this A. We develop a framework and a set of techniques to do simultaneous optimization for a wide variety of problems.

17 pages

*University of Southern California, Los Angeles

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]