{"id":"arxiv/2610.41560","url":"https://arxiv.org/abs/2610.41560","tags":["math.OC"],"score":0,"title":"Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint","domain":"math.OC","source":"arxiv","authors":["Thi Thanh Tu Le","Thorsten Koch"],"reviews":0,"subject":"math.OC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}