论文标题
关于二元多项式优化在无环超图上的复杂性
On the complexity of binary polynomial optimization over acyclic hypergraphs
论文作者
论文摘要
在这项工作中，我们提出了对二进制多项式优化（BPO）计算基本限制的理解，这是在所有二进制点上最大化给定多项式函数的问题。在我们的主要结果中，我们提供了一类新型的BPO，可以从理论和计算的角度有效地解决。实际上，我们为相应的超图是β-酰基的实例提供了强烈的多项式算法。我们注意到，在几种应用中，包括关系数据库方案和树上提起的多次问题，β-囊性假设是自然的。由于我们证明技术的新颖性，我们获得了一种算法，从实际的角度来看，这也很有趣。这是因为我们的算法非常易于实现，并且运行时间是超图的节点和边缘数量非常低的多项式。我们的结果完全解决了BPO在无环超图上的计算复杂性，因为该问题是α-酰基实例上的NP-HARD。我们的算法也可以应用于任何包含β周期的一般BPO问题。对于这些问题，该算法将较小的实例与规则一起返回一个较小的实例，以将较小实例的任何最佳解决方案扩展到原始实例的最佳解决方案。
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 beta-acyclic. We note that the beta-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 alpha-acyclic instances. Our algorithm can also be applied to any general BPO 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.
