A hybrid exact algorithm for complete set partitioning

We benchmark our algorithm against that of Björklund et al. (2009) [8], which runs in O(2n) time given n agents. We observe that the algorithm of Björklund et al. relies on performing arithmetic operations with very large integers, and assumes that any such operation has unit cost. In practice, however, working with large integers on a modern PC is costly. Consequently, when implemented, our O(3n) algorithm outperforms that of Björklund et al. by several orders of magnitude on every problem instance, making ours the fastest exact algorithm for complete set partitioning to date in practice.