Unit Propagation by Means of Coordinate-Wise Minimization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00345948" target="_blank" >RIV/68407700:21230/20:00345948 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-64583-0_60" target="_blank" >https://doi.org/10.1007/978-3-030-64583-0_60</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-64583-0_60" target="_blank" >10.1007/978-3-030-64583-0_60</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Unit Propagation by Means of Coordinate-Wise Minimization

Popis výsledku v původním jazyce

We present a novel theoretical result concerning the applicability of coordinate-wise minimization on the dual problem of linear programming (LP) relaxation of weighted partial Max-SAT that shows that every fixed point of this procedure defines a feasible primal solution. In addition, this primal solution corresponds to the result of a certain propagation rule applicable to weighted Max-SAT. Moreover, we analyze the particular case of LP relaxation of SAT and observe that coordinate-wise minimization on the dual problem resembles unit propagation and also has the same time complexity as a naive unit propagation algorithm. We compare our theoretical results with max-sum diffusion which is a coordinate-wise minimization algorithm that is used to optimize the dual of the LP relaxation of the Max-Sum problem and can in fact perform a different kind of constraint propagation, namely deciding whether a given constraint satisfaction problem (CSP) has non-empty arc consistency closure.

Název v anglickém jazyce

Unit Propagation by Means of Coordinate-Wise Minimization

Popis výsledku anglicky

We present a novel theoretical result concerning the applicability of coordinate-wise minimization on the dual problem of linear programming (LP) relaxation of weighted partial Max-SAT that shows that every fixed point of this procedure defines a feasible primal solution. In addition, this primal solution corresponds to the result of a certain propagation rule applicable to weighted Max-SAT. Moreover, we analyze the particular case of LP relaxation of SAT and observe that coordinate-wise minimization on the dual problem resembles unit propagation and also has the same time complexity as a naive unit propagation algorithm. We compare our theoretical results with max-sum diffusion which is a coordinate-wise minimization algorithm that is used to optimize the dual of the LP relaxation of the Max-Sum problem and can in fact perform a different kind of constraint propagation, namely deciding whether a given constraint satisfaction problem (CSP) has non-empty arc consistency closure.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

<a href="/cs/project/GA19-09967S" target="_blank" >GA19-09967S: Hierarchické architektury pro rozpoznávání</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Machine Learning, Optimization, and Data Science

ISBN

978-3-030-64582-3

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

12

Strana od-do

688-699

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Basel

Místo konání akce

Certosa di Pontignano, Siena

Datum konání akce

19. 7. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—