Greedy Heuristic Guided by Lexicographic Excellence

This article deals with a basic greedy algorithm which, element by element, is able to construct a feasible solution to a wide family of combinatorial optimization problems. The novelty is to guide the greedy algorithm by considering the elements of the problem by order of merit, following a social ranking method. Social rankings come from social choice theory. The method used in the present article, called lexicographic excellence, sorts individual elements on the basis of the performances of groups of elements. In order to validate our approach, we conduct a theoretical analysis on matroid optimization problems, followed by a thorough experimental study on the multi-dimensional knapsack and the maximum weight independent set problem, leading to promising results.