Characterizing Tightness of LP Relaxations by Forbidding Signed Minors
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Weller, Adrian
Abstract
We consider binary pairwise graphical models and provide an exact characterization (necessary and sufficient conditions observing signs of potentials) of tightness for the LP relaxation on the triplet-consistent polytope of the MAP inference problem, by forbidding an odd-K
Description
Keywords
Journal Title
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence
Conference Name
Journal ISSN
Volume Title
Publisher
Association for Uncertainty in Artificial Intelligence