In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multi-objective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal front of the functions which constitute the given objective. Using this idea, we give the first fully polynomial time approximation schemes for the max-min resource allocation problem with a fixed number of agents and for combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions.
Citation
Technical Report, Operations Research Center, Massachusetts Institute of Technology