We consider the problem of determining the minimax regret of a set of utility vectors, where the minimax regret is defined with respect to a given space of possible weight vectors. We present two novel approaches for this problem. The first one improves on an existing method based on the set of undominated utility vectors, by adding maximum regret upper bounds in order to reduce the number of linear programming computations. Our second approach uses a branch-and-bound algorithm that can be applied when the utility vectors are given in the form of sub-utility functions over a set of Boolean variables. Both of our approaches make heavy use of two particular sets of weight vectors, one that approximates the convex hull of the weight space from within, and the other from without. We show that our two approaches complement each other well, with each one having its own combinations of parameters for which it outperforms the other.