Machine Learning Meetings and Events
Group Meetings: Group meetings are held Mondays from 11am to Noon (talk starts 11:10am) in D.L. Pratt 290C unless otherwise noted. Meetings are coordinated by Hugo Larochelle.
Tea Talks: Tea talks are held every Wednesday at 4:00pm in D.L. Pratt 290C. Talks should be simple, accessible, and not exceed 15 minutes. Speakers bring snacks, make tea, and provide a copy of the presented paper.
Group Meeting Oct 26, 2009: Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms
- Speaker: Nevena Lazic
- Abstract:
The Uncapacitated Facility Location Problem (UFLP) is one of the simplest and most widely studied discrete location problems in Operations Research. It is known to be max-SNP hard, and has been tackled via both integer programming methods, randomized heuristics and rho-approximation algorithms.
We find UFLP solutions 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 3-approximation of the optimal UFLP solution. In addition, we characterize several scenarios under which the MPLP solution is guaranteed to be globally optimal.