bounded tree width

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

  • Sourabh
  • 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

    Minimum Color-Degree Perfect b -Matchings

  • Mariia Anapolska
  • Christina Büsing
  • Martin Comis
  • Tabea Brandt
    • Categories Dynamic Programming, Graphs and Matroids Tags , , , , ,

    The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more