---
res:
bibo_abstract:
- 'We consider the MAP-inference problem for graphical models,which is a valued
constraint satisfaction problem defined onreal numbers with a natural summation
operation. We proposea family of relaxations (different from the famous Sherali-Adams
hierarchy), which naturally define lower bounds for itsoptimum. This family always
contains a tight relaxation andwe give an algorithm able to find it and therefore,
solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose
the original probleminto two non-overlapping parts: an easy LP-tight part and
adifficult one. For the latter part a combinatorial solver must beused. As we
show in our experiments, in a number of applica-tions the second, difficult part
constitutes only a small fractionof the whole problem. This property allows to
significantlyreduce the computational time of the combinatorial solver andtherefore
solve problems which were out of reach before.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Stefan
foaf_name: Haller, Stefan
foaf_surname: Haller
- foaf_Person:
foaf_givenName: Paul
foaf_name: Swoboda, Paul
foaf_surname: Swoboda
foaf_workInfoHomepage: http://www.librecat.org/personId=446560C6-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Bogdan
foaf_name: Savchynskyy, Bogdan
foaf_surname: Savchynskyy
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: AAAI@
dct_title: Exact MAP-inference by confining combinatorial search with LP relaxation@
...