The Random QUBO

Karthik Natarajan ()
Additional contact information
Karthik Natarajan: Singapore University of Technology and Design

Chapter Chapter 7 in The Quadratic Unconstrained Binary Optimization Problem, 2022, pp 187-206 from Springer

Abstract: Abstract In this chapter, we discuss instances of QUBO where the input data is random. Such random instances are often analyzed within the topic of “probabilistic combinatorial optimization” and the goal is to study the behavior of the distribution of the optimal value and the distribution of the optimal solution. The introduction of randomness makes the problem more challenging from a computational perspective. We discuss a probabilistic model with dependent random variables where it is possible to extend many of the known computational results from deterministic QUBO to random QUBO. We also review an interesting asymptotic characterization of the random optimal value under independent and identically distributed random variables.

Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-031-04520-2_7

Ordering information: This item can be ordered from
http://www.springer.com/9783031045202

DOI: 10.1007/978-3-031-04520-2_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().