|Publications & Technical Reports|
Semi-Independent Partitioning: A Method for Approximating the Solution to Constraint Optimization ProblemsDavid 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  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.