{"id":"arxiv/2610.16898","url":"https://arxiv.org/abs/2610.16898","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Exponential Local Search in Bounded-Occurrence MAX-CSP","domain":"cs.DS","source":"arxiv","authors":["Sophia Heimann","Hung P. Hoang","Stefan Hougardy"],"reviews":0,"subject":"cs.DS","summary":"We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of $r$ values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}