Abstract
Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-3-Cut. We present a 0.864-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and generalized anticommutation, which may be of independent interest.
Originalsprog | Engelsk |
---|---|
Titel | IEEE Annual Symposium on Foundations of Computer Science |
Publikationsdato | okt. 2024 |
ISBN (Elektronisk) | 979-8-3315-1674-1 |
Status | Udgivet - okt. 2024 |