Making problems easier by multi-objective optimization (in evolutionary computation)

First, we consider the effect of adding objectives to a given problem. Experimental studies show that additional objectives may change the runtime behavior of evolutionary algorithms drastically. We illustrate the effect of adding objectives by considering simple functions and point out by theoretical analyses that this may be both beneficial and obstructive.
Later on, we consider the approximation ability of evolutionary algorithms for the class of covering problems and compare single-objective and multi-objective models for such problems.
We show that optimal solutions can be approximated within a factor of log n, where $n$ is the problem dimension, using a multi-objective approach while the approximation quality obtainable by a corresponding single-objective one may be arbitrarily bad.