Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency

Researchers propose a new cluster-identification method to tighten LP relaxations for MAP-MRF inference.

The technique derives clusters by applying Singleton Arc Consistency to a related CSP instance.

Experiments show better performance than the earlier frustrated-cycles approach.

The advance could improve exact or approximate inference for NP-hard MAP-MRF problems used in computer vision.