Fast Pareto Optimization Using Sliding Window Selection

Many real-world optimization problems face diminishing returns when adding additional elements to a solution and can be formulated in terms of a submodular function [1, 2]. Problems that can be stated in terms of a submodular function include classical combinatorial optimization problems such as the computation of a maximum coverage [3] or maximum cut [4] in graphs as well as regression problems arising in machine learning. Classical approximation algorithms for monotone submodular optimization problems under different types of constraints rely on greedy approaches which select elements with the largest benefit/cost gain according to the gain with respect to the given submodular function and the additional cost with respect to the given constraint [5, 2]. During the last years, evolutionary multi-objective algorithms have been shown to provide the same theoretical worst case performance guarantees on solution quality as the greedy approaches while clearly outperforming classical greedy approximation algorithms in practice [6, 7, 8, 9]. Results are obtained by means of rigorous runtime analysis (see [10, 11] for comprehensive overviews) which is a major tool for the analysis of evolutionary algorithms.