Algebraic Approach to Approximation

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10489333" target="_blank" >RIV/00216208:11320/24:10489333 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3661814.3662076" target="_blank" >https://doi.org/10.1145/3661814.3662076</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3661814.3662076" target="_blank" >10.1145/3661814.3662076</a>

Result language
angličtina
Original language name
Algebraic Approach to Approximation
Original language description
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs. To every valued promise CSP we associate an algebraic object, its so-called valued minion. Our main result shows that the existence of a homomorphism between the associated valued minions implies a polynomial-time reduction between the original CSPs. We also show that this general reduction theorem includes important inapproximability results, for instance, the inapproximability of almost solvable systems of linear equations beyond the random assignment threshold.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2024
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
Proceedings - Symposium on Logic in Computer Science
ISBN
—
ISSN
1043-6871
e-ISSN
2575-5528
Number of pages
14
Pages from-to
—
Publisher name
IEEE Computer Society Press
Place of publication
Washington, D.C.
Event location
Tallinn
Event date
Jul 8, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001275042100010

Similar results(10)