An efficient algorithm for the uncapacitated facility location problem with totally balanced matrix

The uncapacitated facility location problem is considered in case when the transportation matrix has a totally balanced characteristic matrix. Since this problem is equivalent to the minimization problem of a polynomial in Boolean variables, an efficient algorithm is developed in terms of the latter. The idea of the algorithm is based on the fact that the minimization problem of a totally balanced polynomial can be reduced to the minimization problem of a similar polynomial having one fewer variables. (C) 2001 Published by Elsevier Science B.V.