On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization

DOI10.1137/15M1047775zbMath1347.90060DBLPjournals/siamjo/Papp16arXivmath/0701184OpenAlexW1678159847WikidataQ57434178 ScholiaQ57434178MaRDI QIDQ2810549

David Papp

Publication date: 3 June 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0701184

zbMATH Keywords

local optimizationexponential complexitybinary quadratic optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Boolean programming (90C09)

Related Items (1)

Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints

Cites Work

• Equilibria, fixed points, and complexity classes
• How easy is local search?
• Optimality Conditions for the Minimization of Quadratic 0-1 Problems
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem

This page was built for publication: On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization