# Algorithms for the Nearest Assignment Problem

# Algorithms for the Nearest Assignment Problem

## Sara Rouhani, Tahrima Rahman, Vibhav Gogate

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

Main track. Pages 5096-5102.
https://doi.org/10.24963/ijcai.2018/707

We consider the following nearest assignment problem (NAP): given a Bayesian network B and probability value q, find a configuration w of variables in B such that difference between q and the probability of w is minimized. NAP is much harder than conventional inference problems such as finding the most probable explanation and is NP-hard even on independent Bayesian networks (IBNs), which are networks having no edges. Therefore, in order to solve NAP on IBNs, we show how to encode it as a two-way number partitioning problem. This encoding allows us to use greedy poly-time approximation algorithms from the number partitioning literature to yield an algorithm with guarantees for solving NAP on IBNs. We extend this basic algorithm from independent networks to arbitrary probabilistic graphical models by leveraging cutset conditioning and (Rao-Blackwellised) sampling algorithms. We derive approximation and complexity guarantees for our new algorithms and show experimentally that they are quite accurate in practice.

Keywords:

Uncertainty in AI: Approximate Probabilistic Inference

Uncertainty in AI: Graphical Models

Machine Learning: New Problems

Uncertainty in AI: Bayesian Networks