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 multi-objective 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.