论文标题
通过多目标进化算法在分区矩阵限制下最大化的或单调的功能
Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
论文作者
论文摘要
在某些约束下，许多重要的问题可以被视为最大化了次管函数。已证明一种称为GSEMO的简单多目标进化算法有效地实现了良好的近似值。尽管对该主题进行了许多研究，但GSEMO的大多数现有运行时间分析都具有单一的基数约束。在这项工作中，我们将理论结果扩展到概括基数约束的分区矩阵约束，并表明GSEMO通常可以保证多项式预期运行时间内的良好近似性能。此外，在各种分区的矩阵约束下，我们对基线贪婪算法进行了实验比较。结果表明，在二次运行时间内，GSEMO倾向于优于贪婪。
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.
