Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
This work addresses optimization problems in combinatorial settings for researchers and practitioners, but it is incremental as it extends existing theoretical results to a more general constraint type.
The paper tackles the problem of maximizing submodular or monotone functions under partition matroid constraints, extending prior work from single cardinality constraints, and shows that the GSEMO algorithm guarantees good approximation performance with polynomial expected run time, with experiments indicating it tends to outperform a GREEDY baseline in quadratic run time on random graphs.
Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time.