Jianjun Gao

A polynomial case of cardinality constrained quadratic optimization problem

  • Jianjun Gao
  • Duan Li
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , , ,

    We investigate in this paper a fixed parameter polynomial algorithm for the cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size $n$, the number of decision variables, and $s$, the cardinality, if, for some $0

    On Duality Gap in Binary Quadratic Programming

  • Jianjun Gao
  • Duan Li
  • Chunli Liu
  • Xiaoling Sun
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming

    We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness … Read more