arXiv preprint ·
Exponential Local Search in Bounded-Occurrence MAX-CSP
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 objective value, until a local optimum is reached. Our main result is that $(2,2,5)$-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for $(2,2,r)$-MCA for any value of $r$, and our result extends to every $r\ge 5$. In contrast, for $(2,2,2)$-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes
FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
On Collusion-Free Teaching in Planar Graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.