CMU-CS-02-203Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-02-203
Ashish Goel*, Adam Meyerson December 2002
CMU-CS-02-203.ps
Keywords: Algorithms, fairness, majorization, load balancing, routing,
approximation, linear programming, integer programming
- 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 This page maintained by reports@cs.cmu.edu |