On the complexity of local search in unconstrained quadratic binary optimization

DOI10.1137/15M1047775MaRDI QIDQ2810549zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dávid 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

binary quadratic optimizationexponential complexitylocal optimization

Mathematics Subject Classification ID

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

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.

Recommendations

• Complexity of uniqueness and local search in quadratic 0-1 programming
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• Quadratic functions with exponential number of local maxima
• How easy is local search?
• On the quality of local search for the quadratic assignment problem

Cites work

• Equilibria, fixed points, and complexity classes
• How easy is local search?
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Optimality conditions for the minimization of quadratic 0-1 problems

Cited in

(6)

• Checking local optimality in constrained quadratic programming is NP- hard
• Complexity of uniqueness and local search in quadratic 0-1 programming
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• Steepest ascent can be exponential in bounded treewidth problems
• Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)

This page was built for publication: On the complexity of local search in unconstrained quadratic binary optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810549)