Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms

Abstract

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.

arXiv commentPaper accepted for publication in the proceedings of PPSN 2020

References in corpus (5)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Non-monotone submodular maximization under matroid and knapsack constraints
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Efficient Minimization of Decomposable Submodular Functions
• Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid

Cited by in corpus (3)

• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences
• Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints