PreprintCC BY-NC-SA 4.0arXiv
Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
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.
Related
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
- Quadratic fields of values of finite solvable groups
- Continuous-time analysis and algorithms for linear and convex quadratic programs via exactly solvable differential inclusions
- A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems
BibTeX
@misc{le2026polynomially,
title = {{Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint}},
author = {Thi Thanh Tu Le and Thorsten Koch},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41560},
eprint = {2610.41560},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41560},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
AU - Thi Thanh Tu Le
AU - Thorsten Koch
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41560
UR - https://arxiv.org/abs/2610.41560
AB - 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.
ER -