图 书 馆
使用消息传递算法解决无容量限制的设施选址问题Solving the uncapacitated facility location problem using message passing algorithms |
|
| 课程网址: | http://videolectures.net/aistats2010_lazic_stufl/ |
| 主讲教师: | Nevena Lazic |
| 开课单位: | 多伦多大学 |
| 开课时间: | 2010-06-03 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 消息传递算法; 无容量限制的; 设施选址问题 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2021-01-30：nkq |
| 阅读次数: | 55 |