Improved Algorithm for Regret Ratio Minimization in Multi-Objective Submodular Maximization
Yanhao Wang, Jiping Zheng, Fanxu Meng
Abstract
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 improve upon the previous best-known bound on the maximum regret ratio (MRR) of the output of HS-RRM and show that the new bound is nearly asymptotically optimal for any fixed number d of objective functions. Experiments on real-world and synthetic data confirm that HS-RRM achieves lower MRRs than existing algorithms.
BibTeX
@article{Wang_Zheng_Meng_2023, title={Improved Algorithm for Regret Ratio Minimization in Multi-Objective Submodular Maximization}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26472}, DOI={10.1609/aaai.v37i10.26472}, abstractNote={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 improve upon the previous best-known bound on the maximum regret ratio (MRR) of the output of HS-RRM and show that the new bound is nearly asymptotically optimal for any fixed number d of objective functions. Experiments on real-world and synthetic data confirm that HS-RRM achieves lower MRRs than existing algorithms.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Wang, Yanhao and Zheng, Jiping and Meng, Fanxu}, year={2023}, month={Jun.}, pages={12500-12508} }