Improved Algorithm for Regret Ratio Minimization in Multi-Objective Submodular Maximization

Submodular maximization has attracted extensive attention due to its numerous applications in machine learning and artificial intelligence. Many real-world problems require maximizing multiple submodular objective functions at the same time. In such cases, a common approach is to select a representative subset of Pareto optimal solutions with different trade-offs among multiple objectives. To this end, in this paper, we investigate the regret ratio minimization (RRM) problem in multi-objective submodular maximization, which aims to find at most k solutions to best approximate all Pareto optimal solutions w.r.t. any linear combination of objective functions. We propose a novel HS-RRM algorithm by transforming RRM into HITTINGSET problems based on the notions of ϵ-kernel and δ-net, where any α-approximation algorithm for single-objective submodular maximization is used as an oracle. We prove that the maximum regret ratio (MRR) of the 2 output of HS-RRM is bounded by 1 - α + O((k - d)^{- d-1)}, where d is the number of objectives, which improves upon 1 the previous best-known bound of 1 - α + O((k - d)^{- d-1)} and is nearly asymptotically optimal for any fixed d. Experiments on real-world and synthetic data confirm that HS-RRM achieves lower MRRs than existing algorithms.