Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints

Authors

  • Anh Viet Do Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia
  • Frank Neumann Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia

Keywords:

Evolutionary Computation

Abstract

In this study, we consider the subset selection problems with submodular or monotone discrete objective functions under partition matroid constraints where the thresholds are dynamic. We focus on POMC, a simple Pareto optimization approach that has been shown to be effective on such problems. Our analysis departs from singular constraint problems and extends to problems of multiple constraints. We show that previous results of POMC's performance also hold for multiple constraints. Our experimental investigations on random undirected maxcut problems demonstrate POMC's competitiveness against the classical GREEDY algorithm with restart strategy.

Downloads

Published

2021-05-18

How to Cite

Do, A. V., & Neumann, F. (2021). Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12284-12292. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17458

Issue

Section

AAAI Technical Track on Search and Optimization