Set Packing Optimization by Evolutionary Algorithms with Theoretical Guarantees

The set packing problem is a core NP-complete combinatorial optimization problem which aims to find the maximum collection of disjoint sets from a given collection of sets, <i>S</i>, over a ground set, <i>U</i>. Evolutionary algorithms (EAs) have been widely used as general-purpose global optimization methods and have shown promising performance for the set packing problem. While most previous studies are mainly based on experimentation, there is little theoretical investigation available in this area. In this study, we analyze the approximation performance of simplified versions of EAs, specifically the (1+1) EA, for the set packing problem from a theoretical perspective. Our analysis demonstrates that the (1+1) EA can provide an approximation guarantee in solving the <i>k</i>-set packing problem. Additionally, we construct a problem instance and prove that the (1+1) EA beats the local search algorithm on this specific instance. This proof reveals that evolutionary algorithms can have theoretical guarantees for solving NP-hard optimization problems.