Optimization Online


On the complexity of binary polynomial optimization over acyclic hypergraphs

Alberto Del Pia (delpia***at***wisc.edu)
Silvia Di Gregorio (sdigregorio410***at***gmail.com)

Abstract: In this work we consider binary polynomial optimization, which is the problem of maximizing a given polynomial function over all binary points. Our main result is a strongly polynomial-time algorithm for $\beta$-acyclic hypergraphs. The idea behind our algorithm is to successively remove nest points from the hypergraph, until there is only one node left. Once we reach this condition, optimizing the problem becomes trivial. Our result completely settles the computational complexity of binary polynomial optimization over acyclic hypergraphs. In fact, we observe that for $\alpha$-acyclic hypergraphs the problem is strongly NP-hard, and NP-hard to approximate within a constant factor larger than $\frac{16}{17}$ provided that P $\neq$ NP. Our algorithm can also be applied to any general binary polynomial optimization problem that contains $\beta$-cycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance. We assess the effectiveness of this technique via computational experiments on random hypergraphs.

Keywords: binary polynomial optimization; strongly polynomial-time algorithm; acyclic hypergraphs; hardness of approximation; random hypergraphs

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 11/26/2019
Entry Accepted: 11/27/2019
Entry Last Modified: 07/01/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society