On the cardinality of the nondominated set of multi-objective combinatorial optimization problems

Abstract

In this paper we formulate and prove two upper bounds for the nondominated set of multiobjective combinatorial optimization problems with integer coefficients. We also show that under certain assumptions, reasonable and applicable in the majority of practical problems, the number of nondominated points grows following a polynomial function.