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 output of HS-RRM is bounded by 1 -α + O (k -d) -2 d-1 , where d is the number of objectives, which improves upon the previous best-known bound of 1 -α + O (k -d) -1 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.