On the complexity of binary polynomial optimization over acyclic hypergraphs
On the complexity of binary polynomial optimization over acyclic hypergraphs
复制标题
非循环超图上二元多项式优化的复杂度
DOI：
10.1137/1.9781611977073.105
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Silvia Di Gregorio
中科院分区：
文献类型：
--
作者：
Alberto Del Pia;Silvia Di Gregorio
在这项工作中，我们提高了对二进制多项式优化（BPO）计算的基本极限的理解，这是一个在所有二进制点上最大化给定多项式函数的问题。在我们的主要结果中，我们提供了一类新的BPO，可以从理论和计算的角度有效地解决。事实上，对于相应的超图为非循环的实例，我们给出了一个强多项式时间算法。我们注意到，在一些应用程序中，包括关系数据库方案和在树上解除的多切问题，非周期性假设是自然的。由于我们的证明技术的新颖性，我们得到了一个从实用的角度来看也很有趣的算法。这是因为我们的算法非常容易实现，并且运行时间是超图的节点和边的数量非常低程度的多项式。我们的结果完全解决了非环超图上BPO的计算复杂性，因为问题是非环上的NP-hard问题。该算法也可以应用于任何包含-循环的一般业务流程外包问题。对于这些问题，该算法返回一个较小的实例，并提供一个规则，将较小实例的任何最优解扩展为原始实例的最优解。
In this work, we advance the understanding of the fundamental limits of computation for binary polynomial optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whose corresponding hypergraph is-acyclic. We note that the-acyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NP-hard on-acyclic instances. Our algorithm can also be applied to any general BPO problem that contains-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.