On the complexity of local search in unconstrained quadratic binary optimization
classification
🧮 math.OC
keywords
localbinaryquadraticsearchalgorithmcasecomplexityconsider
read the original abstract
We consider the problem of finding a local minimum of a binary quadratic function, and show by an elementary construction that every descending local search algorithm takes exponential time in the worst case.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.