Conditions Beyond Treewidth for Tightness of Higher-order LP Relaxations

被引：0
作者：
Rowland, Mark [1 ]
Pacchiano, Aldo [2 ]
Weller, Adrian [1 ]
机构：
[1] Univ Cambridge, Cambridge, England
[2] Univ Calif Berkeley, Berkeley, CA USA
来源：
ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 54 | 2017年 / 54卷
基金：
英国工程与自然科学研究理事会;
关键词：
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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.
引用
收藏
页码：10 / 18
页数：9
相关论文
共 33 条
  • [1] [Anonymous], 2009, THESIS
  • [2] [Anonymous], 2018, Graph theory
  • [3] [Anonymous], 1953, Michigan Mathematical Journal, DOI DOI 10.1307/MMJ/1028989917
  • [4] FORBIDDEN MINORS CHARACTERIZATION OF PARTIAL 3-TREES
    ARNBORG, S
    PROSKUROWSKI, A
    CORNEIL, DG
    [J]. DISCRETE MATHEMATICS, 1990, 80 (01) : 1 - 19
  • [5] Batra D., 2011, AISTATS
  • [6] Chandrashekaran V, 2008, P 24 C UNC ART INT, P70
  • [7] Hybrid tractability of valued constraint problems
    Cooper, Martin C.
    Zivny, Stanislav
    [J]. ARTIFICIAL INTELLIGENCE, 2011, 175 (9-10) : 1555 - 1569
  • [8] Deza M. M., 1997, GEOMETRY CUTS METRIC, V2, DOI 10.1007/978-3-642-04295-9
  • [9] Learning Graphical Model Parameters with Approximate Marginal Inference
    Domke, Justin
    [J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2013, 35 (10) : 2454 - 2467
  • [10] Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
    Eaton, Frederik
    Ghahramani, Zoubin
    [J]. NEURAL COMPUTATION, 2013, 25 (05) : 1213 - 1260
1234