Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918499615506432 |
|---|---|
| author | Lev-Ran, Asaf Arkhipov, Pavel Kolmogorov, Vladimir |
| author_facet | Lev-Ran, Asaf Arkhipov, Pavel Kolmogorov, Vladimir |
| contents | We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling this NP-hard problem in practice is to solve its natural LP relaxation and then iteratively tighten the relaxation by adding clusters. Based on some theoretical observations, we propose a new technique for identifying such clusters. It works by running the Singleton Arc Consistency algorithm in a certain CSP instance. Experimental results indicate that the new tightening technique outperforms the previous approach by [Sontag et al. UAI 2012] that searches for frustrated cycles. Our code will be made available at https://github.com/vnk-ist/MAP-MRF/. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13392 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency Lev-Ran, Asaf Arkhipov, Pavel Kolmogorov, Vladimir Data Structures and Algorithms We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling this NP-hard problem in practice is to solve its natural LP relaxation and then iteratively tighten the relaxation by adding clusters. Based on some theoretical observations, we propose a new technique for identifying such clusters. It works by running the Singleton Arc Consistency algorithm in a certain CSP instance. Experimental results indicate that the new tightening technique outperforms the previous approach by [Sontag et al. UAI 2012] that searches for frustrated cycles. Our code will be made available at https://github.com/vnk-ist/MAP-MRF/. |
| title | Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.13392 |