Fast Heuristics and Approximation Algorithms

Abraham P. Punnen ()
Additional contact information
Abraham P. Punnen: Simon Fraser University

Chapter Chapter 8 in The Quadratic Unconstrained Binary Optimization Problem, 2022, pp 207-240 from Springer

Abstract: Abstract This chapter discusses theoretical analysis of approximation algorithms for QUBO and the Ising QUBO. We point out that the standard performance measure of relative performance ratio is not suitable for analysing the quality of approximation algorithms for the general versions of QUBO and the Ising QUBO. Thus, polynomial time approximation algorithms are considered and analyzed for the general problems using normalized relative error and domination analysis. More specifically, we discuss no worse than average performance bounds and how to improve them. Also, we present polynomial time approximation algorithms for QUBO and the Ising QUBO with a constant domination ratio. Then, the standard performance ratio of polynomial time approximation algorithms is considered for special cases of the Ising QUBO and QUBO. Relationships between 𝜖-approximation algorithms for QUBO and the Ising QUBO are established when the associated data is specially structured. Further, a polynomial time 1 2 Δ $$\frac {1}{2\Delta }$$ -approximation algorithm and a polynomial time 1 log n $$\frac {1}{\log n}$$ -approximation algorithm, in expectation, are presented for the Ising QUBO when the cost matrix has all diagonal entries zero and Δ is the maximum degree of a node in the associated support graph. Performance ratio of approximation algorithms for other special cases are briefly discussed.

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_8

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

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

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 ().