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 language | English |
---|---|
Title of host publication | The Quadratic Unconstrained Binary Optimization Problem |
Subtitle of host publication | Theory, Algorithms, and Applications |
Place of Publication | Cham |
Publisher | Springer Nature Switzerland AG |
Pages | 57-95 |
Number of pages | 38 |
ISBN (Electronic) | 978-3-031-04520-2 |
DOIs | |
Publication status | Published - 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)