  


On the complexity of binary polynomial optimization over acyclic hypergraphs
Alberto Del Pia (delpiawisc.edu) Abstract: In this work we consider binary polynomial optimization, which is the problem of maximizing a polynomial function over all binary points. We settle the computational complexity of this problem over acyclic hypergraphs. Our main result is a strongly polynomialtime 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. Then, we show that for $\alpha$acyclic hypergraphs the problem is strongly NPhard, and NPhard 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 for the smaller instance to an optimal solution for the original instance. We assess the effectiveness of this technique via computational experiments on random hypergraphs. Keywords: binary polynomial optimization; strongly polynomialtime algorithm; acyclic hypergraphs; hardness of approximation; random hypergraphs Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 11/26/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  