Algorithms for the Nearest Assignment Problem
DescriptionWe propose the following problem, named nearest assignment problem (NAP), in probabilistic graphical models: given a graphical model M and a real number q, find an assignment ω to all variables in M such that the difference between q and probability (or weight) of ω according to M is minimized. NAP is NP-hard. The most probable explanation (MPE) or maximum-a-posteriori (MAP), which are NP-hard inference queries in probabilistic graphical models, are special cases of NAP. We encoded NAP as a two-way number partitioning problem, which is NP-hard as well, on independent graphical models (networks without having any edges). We used polynomial time approximation algorithms with guarantees to solve NAP as a two-way number partition problem. We introduced novel techniques that combine two-way number partitioning, cutset conditioning, local search, and sampling algorithms with approximation guarantees to solve NAP on arbitrary graphical models (networks having edges). Our experiments show that our algorithms are quite accurate.