mlsanityData to 14 Oct 2026

Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems

arXiv 1911.08043 ↗First posted 18 Nov 2019cs.DS cond-mat.stat-mech cs.CCcited by 3

Not on the map. Why?

Abstract (arXiv)

We discuss several mappings from well-known NP-hard problems to Quadratic Unconstrained Binary Optimisation problems which are treated incorrectly by Lucas. We provide counterexamples and correct the mappings. We also extend the body of QUBO formulations of NP-complete and NP-hard optimisation problems by discussing additional problems.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). First posted on arXiv 18 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 1.

3 papers.

  1. 2022Black Box Optimization Using QUBO and the Cross Entropy Methodcited by 3
  2. 2023QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packingcited by 1
  3. 2024Optimizing Sensor Redundancy in Sequential Decision-Making Problemscited by 0