2178. Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
Invited abstract in session TA-2: Combinatorial Optimization, stream Discrete and Combinatorial Optimization.
Thursday, 8:45-10:15Room: H4
Authors (first author is the speaker)
| 1. | Thi Thanh Tu Le
|
| Mathematics and Natural Sciences, TU Berlin/ ZIB | |
| 2. | Thorsten Koch
|
| Applied Algorithmic Intelligence Methods, ZIB / TU Berlin |
Abstract
Quadratic unconstrained binary optimization (QUBO) problems and one of their variants, the quadratic binary program with a fixed cardinality constraint, are both well-known NP-hard problems. In some cases, QUBOs can be solved in polynomial time due to special structural properties of the cost matrix; however, this tractability no longer holds when a fixed cardinality constraint is imposed. We explore structural conditions on the cost matrix that lead to polynomial-time solvability of the quadratic binary optimization problem with a fixed cardinality constraint.
Keywords
- Computational Complexity
- Combinatorial Optimization
Status: accepted
Back to the list of papers