Greedy Hypervolume Subset Selection in Low Dimensions

Area of Science:

• Multi-objective optimization
• Computational geometry
• Algorithm design

Background:

• The Hypervolume Subset Selection Problem (HSSP) aims to find a subset of nondominated points that maximizes the hypervolume indicator.
• This problem is crucial for multiobjective selection, archiving strategies, and Pareto-front approximation for visualization and decision-making.
• Existing efficient algorithms for HSSP are limited to the 2-dimensional case with a time complexity of O(n^2).

Purpose of the Study:

• To develop efficient greedy algorithms for the HSSP in 2 and 3 dimensions.
• To improve the time complexity of solving the HSSP, particularly for higher dimensions.
• To enhance the approximation performance of the hypervolume indicator.

Main Methods:

• The study proposes greedy algorithms leveraging the monotone submodular property of the hypervolume indicator.
• The algorithms are designed for both 2 and 3-dimensional HSSP.
• Time complexity analysis is performed for the proposed algorithms.

Main Results:

• New greedy algorithms for HSSP in 2 and 3 dimensions are presented.
• The proposed 2D algorithm achieves a time complexity of O(n^2), matching existing exact algorithms.
• The algorithms offer improved approximation factors for the HSSP, outperforming previous results.

Conclusions:

• The developed greedy algorithms provide efficient solutions for the HSSP in 2 and 3 dimensions.
• These algorithms significantly advance the state-of-the-art in Pareto-front approximation and multi-objective optimization.
• The findings contribute to more effective visualization and decision-making in complex multi-objective scenarios.