On the complexity of local search in unconstrained quadratic binary optimization

2007/01/05 by Dávid Papp, Papp, Dávid
Computer Science · Engineering · Mathematics · #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems #Optimization and Search Problems #math.OC #msc:68Q25 #msc:90C09 #msc:90C20

paper · pdf · doi:10.48550/arxiv.math/0701184

Minor update in 2016: simplified construction

arxiv created 2016/05/13 · arxiv updated 2016/05/16

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.

Related

• Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs
• Finding One Local Optimum Is Easy -- but What About Two?
• A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization
• Simple Local Search Problems that are Hard to Solve
• Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems