A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

Abstract. In this paper, we propose a general framework for design-ing fully polynomial time approximation schemes for combinatorial opti-mization problems, in which more than one objective function are com-bined into one using any norm. The main idea is to exploit the approx-imate Pareto-optimal frontier for multi-criteria optimization problems. Using this approach, we obtain an FPTAS for a novel resource allo-cation problem, for the problem of scheduling jobs on unrelated par-allel machines, and for the Santa Claus problem, when the number of agents/machines is fixed, for any norm, including the l∞-norm. More-over, either FPTAS can be implemented in a manner so that the space requirements are polynomial in all input parameters. We also give ap-proximation algorithms and hardness results for the resource allocation problem when the number of agents is not fixed. 1