Complexity and Polynomially Solvable Special Cases of QUBO

Eranda Çela*, Abraham P. Punnen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The quadratic unconstrained binary optimization problem (QUBO) is equivalent to a number of prominent combinatorial and discrete optimization problems and generalizes many others. In this chapter we will discuss the computational complexity aspects of the problem along with tractable special cases. Many of those results are derived from the related properties of the optimization problems which are equivalent to or generalized by QUBO.
Original languageEnglish
Title of host publicationThe Quadratic Unconstrained Binary Optimization Problem
Subtitle of host publicationTheory, Algorithms, and Applications
Place of PublicationCham
PublisherSpringer Nature Switzerland AG
Pages57-95
Number of pages38
ISBN (Electronic)978-3-031-04520-2
DOIs
Publication statusPublished - Aug 2022

ASJC Scopus subject areas

  • Control and Optimization
  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Basic - Fundamental (Grundlagenforschung)

Cite this