The Rise of Plurimorphisms: Algebraic Approach to Approximation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912218025558016 |
|---|---|
| author | Barto, Libor Butti, Silvia Kazda, Alexandr Viola, Caterina Živný, Stanislav |
| author_facet | Barto, Libor Butti, Silvia Kazda, Alexandr Viola, Caterina Živný, Stanislav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15186 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Rise of Plurimorphisms: Algebraic Approach to Approximation Barto, Libor Butti, Silvia Kazda, Alexandr Viola, Caterina Živný, Stanislav Computational Complexity Discrete Mathematics Logic in Computer Science 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. |
| title | The Rise of Plurimorphisms: Algebraic Approach to Approximation |
| topic | Computational Complexity Discrete Mathematics Logic in Computer Science |
| url | https://arxiv.org/abs/2401.15186 |