## Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms

• The hypervolume subset selection problem consists of finding a subset, with a given cardinality, of a nondominated set of points that maximizes the hypervolume indicator. This problem arises in selection procedures of population-based heuristics for multiobjective optimization, and for which practically efficient algorithms are strongly required. In this article, we provide two new formulations for the two-dimensional variant of this problem. The first is an integer programming formulation that can be solved by solving its linear relaxation. The second formulation is a $$k$$-link shortest path formulation on a special digraph with Monge property that can be solved by dynamic programming in $$\mathcal{O}(n^2)$$ time complexity. This improves upon the existing result of $$O(n^3)$$ in Bader.