Unit Propagation by Means of Coordinate-Wise Minimization

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Unit Propagation by Means of Coordinate-Wise Minimization

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10100 - Mathematics

Project

<a href="/en/project/GA19-09967S" target="_blank" >GA19-09967S: Compositional Architectures for Pattern Recognition</a><br>

Continuities

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

Publication year

2020

Confidentiality

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

Article name in the collection

Machine Learning, Optimization, and Data Science

ISBN

978-3-030-64582-3

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

12

Pages from-to

688-699

Publisher name

Springer Nature Switzerland AG

Place of publication

Basel

Event location

Certosa di Pontignano, Siena

Event date

Jul 19, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—