# RRMS

Description : This package includes the Python code of RRMS [1], Polytope [2], RRMS* and SingleObj. The corresponding datasets are also included. RRMS [1] solves the multi-objective submodular maximization problem by minimizing the regret ratio. Concretely, RRMS applies an existing $\alpha$-approximation algorithm to solve each objective independently at the first stage. Then it samples $k-d$ representative weight vectors to approximate the whole non-negative unit weight vector space and applies the $\alpha$-approximation algorithm to solve the linear combination of objectives w.r.t. the sampled weight vectors. Lastly, RRMS returns all the obtained solutions. Polytope is the existing algorithm [2] for multi-objective submodular maximization, while RRMS* and SingleObj are two baselines.

References: [1] Multi-objective submodular maximization by regret ratio minimization with theoretical guarantee. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI'21), Virtual, 2021, to appear. [2] Regret ratio minimization in multi-objective submodular function maximization. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17), pp. 905–911, Austin, TX, 2017.