Paperlane

no. 6 · Monday 2 November 2026

Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint

Thi Thanh Tu Le and Thorsten Koch

math.OC · 7 pp

Abstract

Quadratic Unconstrained Binary Optimization (QUBO) problems and their variant with a fixed cardinality constraint are both well-known NP-hard problems. While certain structural properties of the cost matrix can make some QUBO instances solvable in polynomial time, this advantage typically disappears once a cardinality constraint is added. In this work, we investigate specific structural conditions on the cost matrix under which the constrained version-quadratic binary optimization with a fixed cardinality-remains tractable.

comments
7 pages, it was accepted for publication for Operations Research Proceedings 2025/ Annual International Conference of the German Operations Research Society
fields
Optimization and Control
pdf ↗ page arXiv:2610.41560 ↗