A general algorithmic pattern for finding lexicographic max-ordering solutions to combinatorial multicriteria optimization problems

Abstract We study a particular class of greedy algorithms for combinatorial optimization problems and present a generalized version of this algorithmic pattern encompassing several previously published algorithms. We analyze the properties of the solutions produced by such algorithms and provide proofs of their optimality through the concept of lexicographic max-ordering . By presenting a unified formulation of this class of greedy algorithms, we hope to facilitate the development of new such algorithms and to provide a deeper understanding on the properties of existing ones. To illustrate the utility of our results, we present two case studies, where we study two previously published optimization algorithms and show that they can be seen as instances of the proposed general algorithmic pattern. In doing so, we provide alternative proofs of correctness for these algorithms and draw new conclusions about their properties.