Title:
Message-Passing-Algorithms
Download
Description: The Uncapacitated Facility Location Prob-
lem (UFLP) is one of the most widely stud-
ied discrete location problems, whose appli-
cations arise in a variety of settings. We
tackle the UFLP using probabilistic infer-
ence in a graphical model- an approach that
has received little attention in the past. We
show that the fi xed points of max-product
linear programming (MPLP), a convexifi ed
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 eval-
uate the performance of both max-sum and
MPLP empirically on metric and non-metric
problems, demonstrating the advantages of
the 3-approximation construction and algo-
rithm applicability to non-metric instances.
To Search:
File list (Check if you may need any files):
Message Passing Algorithms..pdf
