# Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms

[edit]

Nevena Lazic,
Brendan Frey,
Parham Aarabi
;

Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:429-436, 2010.

#### Abstract

The Uncapacitated Facility Location Problem (UFLP) is one of the most widely studied discrete location problems, whose applications arise in a variety of settings. We tackle the UFLP using probabilistic inference in a graphical model - an approach that has received little attention in the past. We show that the fixed points of max-product linear programming (MPLP), a convexified version of the max-product algorithm, can be used to construct a solution with a 3-approximation guarantee for metric UFLP instances. In addition, we characterize some scenarios under which the MPLP solution is guaranteed to be globally optimal. We evaluate the performance of both max-sum and MPLP empirically on metric and non-metric problems, demonstrating the advantages of the 3-approximation construction and algorithm applicability to non-metric instances.

#### Related Material