Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems
For researchers in evolutionary computation and combinatorial optimization, this work provides a principled multitasking framework that reduces computational cost when solving multiple related submodular maximization problems.
The paper introduces multitasking Pareto optimization for monotone submodular problems with different knapsack constraints, showing that sharing solutions across problems yields significant runtime improvements over independent runs, achieving a (1-1/e)-approximation.
Pareto optimization via evolutionary multi-objective algorithms has been shown to efficiently solve constrained monotone submodular functions. Traditionally when solving multiple problems, the algorithm is run for each problem separately. We introduce multitasking formulations of these problems that are an effective way to solve multiple related problems with a single run. In our setting the given problems share a monotone submodular function $f$ but have different knapsack constraints. We examine the case where elements within a constraint have the same cost and show that our multitasking formulations result in small Pareto fronts. This allows the population to share solutions between all problems leading to significant improvements compared to running several classical approaches independently. Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a $(1-1/e)$-approximation for each of the given problems. Our experimental investigations for the maximum coverage problem give further insight into the dynamics behind how the approach works and doesn't work in practice for problems where elements within a constraint also have varied costs.