  Recently, it has been shown that the enumeration of Minimal Correction
Subsets (MCS) of Boolean formulas allows solving Multi-Objective Boolean
Optimization (MOBO) formulations. However, a major drawback of this approach is
that most MCSs do not correspond to Pareto-optimal solutions. In fact, one can
only know that a given MCS corresponds to a Pareto-optimal solution when all
MCSs are enumerated. Moreover, if it is not possible to enumerate all MCSs,
then there is no guarantee of the quality of the approximation of the Pareto
frontier. This paper extends the state of the art for solving MOBO using MCSs.
First, we show that it is possible to use MCS enumeration to solve MOBO
problems such that each MCS necessarily corresponds to a Pareto-optimal
solution. Additionally, we also propose two new algorithms that can find a (1 +
{\varepsilon})-approximation of the Pareto frontier using MCS enumeration.
Experimental results in several benchmark sets show that the newly proposed
algorithms allow finding better approximations of the Pareto frontier than
state-of-the-art algorithms, and with guaranteed approximation ratios.
