Abstract
The paper addresses the problem of computing lower bounds on the optimal costs associated with each unary assignment of a value to a variable in combinatorial optimization problems. This task is instrumental in probabilistic reasoning and is also important for the development of admissible heuristic functions that can guide search algorithms for optimal solutions. The paper presents UD-MB, a new algorithm that applies the mini-bucket elimination idea [Dechter and Rish, 1997] to accomplish this task. We show empirically that UD-MB may achieve a substantial speed up over a brute-force approximation method via mini-buckets.