Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems

Researchers Liam Wigney and Frank Neumann have published a paper introducing a new multitasking approach for evolutionary multi-objective algorithms. Traditionally, algorithms like these are run separately for each instance of a constrained optimization problem. Their novel formulation allows a single algorithm run to solve multiple related problems that share a core monotone submodular function but have different knapsack constraints. This enables the algorithm's population to share beneficial solutions across all problems simultaneously, leading to smaller, more manageable Pareto fronts and significant efficiency gains compared to running classical approaches independently for each task.

Using rigorous runtime analysis, the researchers proved that their multitasking approaches can achieve a (1-1/e)-approximation—a standard benchmark for near-optimal solutions in submodular optimization—for each of the given problems. Their experimental investigations focused on the maximum coverage problem, a classic example of a monotone submodular function. These experiments provided crucial insight into the practical dynamics of the approach, revealing both how it works effectively and the conditions under which it may struggle, particularly for problems where elements within a constraint have varied costs instead of uniform costs.