Complexity and Polynomially Solvable Special Cases of QUBO

Eranda Çela; Abraham P. Punnen

doi:10.1007/978-3-031-04520-2_3

Complexity and Polynomially Solvable Special Cases of QUBO

Eranda Çela^*, Abraham P. Punnen

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in Buch/Bericht

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.

Originalsprache	englisch
Titel	The Quadratic Unconstrained Binary Optimization Problem
Untertitel	Theory, Algorithms, and Applications
Erscheinungsort	Cham
Herausgeber (Verlag)	Springer Nature Switzerland AG
Seiten	57-95
Seitenumfang	38
ISBN (elektronisch)	978-3-031-04520-2
DOIs	https://doi.org/10.1007/978-3-031-04520-2_3
Publikationsstatus	Veröffentlicht - Aug. 2022

ASJC Scopus subject areas

Steuerung und Optimierung
Theoretische Informatik
Diskrete Mathematik und Kombinatorik

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Zugriff auf Dokument

10.1007/978-3-031-04520-2_3

Dieses zitieren

@inbook{0ae7ae3d91b44dbfbf76151847f7e3b7,

title = "Complexity and Polynomially Solvable Special Cases of QUBO",

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.",

author = "Eranda {\c C}ela and Punnen, {Abraham P.}",

year = "2022",

month = aug,

doi = "10.1007/978-3-031-04520-2_3",

language = "English",

pages = "57--95",

booktitle = "The Quadratic Unconstrained Binary Optimization Problem",

publisher = "Springer Nature Switzerland AG",

address = "Switzerland",

}

TY - CHAP

T1 - Complexity and Polynomially Solvable Special Cases of QUBO

AU - Çela, Eranda

AU - Punnen, Abraham P.

PY - 2022/8

Y1 - 2022/8

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-04520-2_3

DO - 10.1007/978-3-031-04520-2_3

M3 - Chapter

SP - 57

EP - 95

BT - The Quadratic Unconstrained Binary Optimization Problem

PB - Springer Nature Switzerland AG

CY - Cham

ER -

Complexity and Polynomially Solvable Special Cases of QUBO

Abstract

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Zugriff auf Dokument

Fingerprint

Dieses zitieren