--- 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_identifier: - UT:000485488906082 dct_language: eng dct_publisher: AAAI Press@ dct_title: Exact MAP-inference by confining combinatorial search with LP relaxation@ ...