Computer Science Department
School of Computer Science, Carnegie Mellon University
Simultaneous Optimization via Approximate
Ashish Goel*, Adam Meyerson
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.
*University of Southern California, Los Angeles