论文标题
帕累托优化用于用动态分区矩阵约束的子集选择
Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints
论文作者
论文摘要
在这项研究中，我们考虑了在阈值是动态的，在分区矩阵约束下具有子集或单调离散目标函数的子集选择问题。我们专注于POMC，这是一种简单的帕累托优化方法，已被证明对此类问题有效。我们的分析偏离了奇异的约束问题，并扩展到了多个约束的问题。我们表明，POMC性能的先前结果也适用于多个约束。我们对随机无方向性问题的实验研究表明，通过重新启动策略，POMC对经典贪婪算法的竞争力。
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.
