Fast Heuristics and Approximation Algorithms

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.