# Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs

arXiv: https://arxiv.org/abs/1708.03314 · HTML: https://mlsanity.com/paper/1708.03314/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2017.

## Built on by (most cited first, 4 of 4)

- [Self-Supervised Training with Autoencoders for Visual Anomaly Detection](https://mlsanity.com/paper/2206.11723/) (2022)
- [MPE inference using an Incremental Build-Infer-Approximate Paradigm](https://mlsanity.com/paper/2206.01954/) (2022)
- [Noise & pattern: identity-anchored Tikhonov regularization for robust structural anomaly detection](https://mlsanity.com/paper/2511.07233/) (2025)
- [Rethinking Structural Anomaly Detection: From Decision Boundaries to Projection Operators](https://mlsanity.com/paper/2606.15280/) (2026)

## Abstract (arXiv)

Markov random fields (MRFs) are a powerful tool for modelling statistical dependencies for a set of random variables using a graphical representation. An important computational problem related to MRFs, called maximum a posteriori (MAP) inference, is finding a joint variable assignment with the maximal probability. It is well known that the two popular optimisation techniques for this task, linear programming (LP) relaxation and dual decomposition (DD), have a strong connection both providing an optimal solution to the MAP problem when a corresponding LP relaxation is tight. However, less is known about their relationship in the opposite and more realistic case. In this paper, we explain how the fully integral assignments obtained via DD partially agree with the optimal fractional assignments via LP relaxation when the latter is not tight. In particular, for binary pairwise MRFs the corresponding result suggests that both methods share the partial optimality property of their solutions.