Many applications in operations research require the simultaneous optimization of multiple (typically mutually opposing) objective functions. Since the general problem is usually computationally intractable, bicriteria optimization restricts itself to two objectives while approximate optimization aims at solutions that differ from the optimal one by not more than a given factor.
This paper addresses a variant of approximate bicriteria optimization in which both objectives have lower and upper bounds, and it only seeks solutions for which the first objective does not exceed a given budget. It is shown how a polynomial-time approximate solution of the bicriteria problem can be obtained from any polynomial-time algorithm that approximately solves the problem of minimizing the weighted sum of both objective functions; this is achieved by solving finitely many instances of this single criterion problem. If the weighted sum optimization algorithm actually gives exact solutions, then the complexity of the method can be further improved by applying a bisection-style search in the solution space. However, the technique is restricted to minimization: unless P=NP, corresponding solutions for the maximization problem cannot be obtained in polynomial time.
The paper is self-contained: it presents all necessary mathematical background, the history of the problem, previously presented approaches, and how the new approach can be applied where previous ones have failed. Furthermore, it tabulates a list of concrete combinatorial optimization problems for which the new technique yields the best-known results. Further work will aim at generalizing the technique to more than two objectives and at applying other single-criteria algorithms.