Conditions Beyond Treewidth for Tightness of Higher-Order LP Relaxations
Abstract
Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integral vertex then the solution is guaranteed to be exact and we say that the relaxation is tight. We consider binary pairwise models and introduce new methods which allow us to demonstrate refined conditions for tightness of LP relaxations in the Sherali-Adams hierarchy. Our results include showing that for higher order LP relaxations, treewidth is not precisely the right way to characterize tightness. This work is primarily theoretical, with insights that can improve efficiency in practice.
Cite
Text
Rowland et al. "Conditions Beyond Treewidth for Tightness of Higher-Order LP Relaxations." International Conference on Artificial Intelligence and Statistics, 2017.Markdown
[Rowland et al. "Conditions Beyond Treewidth for Tightness of Higher-Order LP Relaxations." International Conference on Artificial Intelligence and Statistics, 2017.](https://mlanthology.org/aistats/2017/rowland2017aistats-conditions/)BibTeX
@inproceedings{rowland2017aistats-conditions,
title = {{Conditions Beyond Treewidth for Tightness of Higher-Order LP Relaxations}},
author = {Rowland, Mark and Pacchiano, Aldo and Weller, Adrian},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2017},
pages = {10-18},
url = {https://mlanthology.org/aistats/2017/rowland2017aistats-conditions/}
}