Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
math.OC
Submitted: 2026-10-30
Updated: 2026-10-30
Comments: 7 pages, it was accepted for publication for Operations Research Proceedings 2025/ Annual International Conference of the German Operations Research Society
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: Quadratic Unconstrained Binary Optimization (QUBO) problems and their variant with a fixed cardinality constraint are both well-known NP-hard problems.
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 papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise