2024/03/04 by Suprovat Ghoshal, Ghoshal, Suprovat, Konstantin Makarychev +3 · 3 citations
Computer Science · Decision Sciences · Engineering · #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Scheduling and Optimization Algorithms #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2403.02212
openalex publication_date 2024/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following. 1. For Max-Cut and Max 2-Lin, we design an algorithm that yields near-optimal solutions when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees. 2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still 1/2 + η hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is 1/2 + η hard to approximate even when the average degree of the instance is linear in the number of variables.