fixed parameter polynomial algorithm

New Proofs of Exact LP Reformulations for Binary Polynomial Optimization with Bounded Treewidth

  • Sourabh Kumar Choudhary
  • Santanu S. Dey
  • Nikolaos Sahinidis
    • Categories Combinatorial Optimization Tags , ,

    In this work, we revisit binary polynomial optimization (BPO) problems with limited treewidth of the associated graph. We provide alternate proofs of the exactness of a reformulated linear program (LP) with O(n.2^d) variables, n being the number of variables and d being the treewidth of the associated graph. The first proof relies on expressing any … Read more

    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