Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms
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.
Cite
Text
Lazic et al. "Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.Markdown
[Lazic et al. "Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.](https://mlanthology.org/aistats/2010/lazic2010aistats-solving/)BibTeX
@inproceedings{lazic2010aistats-solving,
title = {{Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms}},
author = {Lazic, Nevena and Frey, Brendan and Aarabi, Parham},
booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics},
year = {2010},
pages = {429-436},
volume = {9},
url = {https://mlanthology.org/aistats/2010/lazic2010aistats-solving/}
}