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. 905911, Austin, TX, 2017.

ATTN: This package is free for academic usage. You can run it at your own risk. For other purposes, please contact Dr. Chao Qian (qianc@lamda.nju.edu.cn).

Requirement: The package was developed with Python. It relies on these python packages: numpy, cvxopt, cvxpy.

ATTN2: This package was developed by Mr. Chao Feng (chaofeng@mail.ustc.edu.cn). For any problem concerning the code, please feel free to contact Mr. Feng.

Download: code (1MB)