Computer Science Department
School of Computer Science, Carnegie Mellon University


Simultaneous Optimization via Approximate
Majorization for Concave Profits or Convex Costs

Ashish Goel*, Adam Meyerson

December 2002

Keywords: Algorithms, fairness, majorization, load balancing, routing, approximation, linear programming, integer programming

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