Weighted search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w. The current work extends the previous investigation of weighted search algorithms with the mini-bucket heuristic. We perform empirical analysis of various such algorithms with more advanced heuristics such as Join-Graph Linear Programming and Mini-Bucket Elimination with Moment Matching.