Semi-Independent Partitioning: A Method for Approximating the Solution to Constraint Optimization Problems
David Larkin
In this paper we introduce a new method for approximating the solution to constraint optimization problems called semi-independent partitioning. We show that our method is a strict generalization of the mini buckets algorithm [3] which allows a richer and more e.ective set of approximation strategies. We demonstrate with theoretical analysis and empirical results that it generally produces a better answer than mini buckets in much less time.