Study of natural optimization issues in maximum constraints
Pasin Manurangsi and Dana Moshkovitz
Progress in Signals and Telecommunication Engineering, Vol. 13, No. 1, 2024.
DOI: https://doi.org/10.6025/pste/2024/13/1/44-63
Link: https://www.dline.info/pste/fulltext/v13n1/pstev13n1_3.pdf
Abstract:
Maximum constraint satisfaction problem (Max CSP) is a problem of great interest in approximation algorithms since it encapsulates many natural optimization problems. The goal is to find an assignment to all the variables that satisfy as many constraints as possible. In this work, our primary focus is the case where each constraint depends on exactly k = 2 variables and the large alphabet size. This case has been intensively researched regarding the hardness of approximation and multi-prover games.