Article ID Journal Published Year Pages File Type
6853168 Artificial Intelligence 2016 47 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, , , , ,