Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints
This work provides an incremental theoretical extension for the POMC algorithm, showing its applicability to multiple constraints for researchers working on combinatorial optimization.
This paper addresses subset selection problems with submodular or monotone discrete objective functions under dynamic partition matroid constraints. The authors demonstrate that the Pareto Optimization for Multiple Constraints (POMC) approach, previously effective for singular constraints, maintains its performance for multiple constraints. Experiments on random undirected maxcut problems show POMC is competitive with the classical GREEDY algorithm with a restart strategy.
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.