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.


翻译:在这项工作中,我们增进了对二进制多元优化(BPO)计算基本限值的理解,这是在所有二进制点上最大限度地实现给定多式功能的问题。在我们的主要结果中,我们提供了一种新型的BPO,从理论和计算角度都能有效解决。事实上,我们给相应的高光度高光度高光度高光度的事例提供了强烈的多元时间算法。我们注意到,在包括关系数据库计划和树上的多重切割问题在内的若干应用中,乙周期性假设是自然的。由于我们检验技术的新颖性,我们获得了一种也从实际角度引人注意的算法。这是因为我们的算法非常简单,运行时间是高光度节点和边缘非常低的多元数。我们的结果完全解决了BPO相对于环度高光度高光度高光度的计算复杂性,因为问题在阿尔法周期上是硬化的。由于我们的验证技术的新颖性,我们也可以从一个实用角度获得一种有趣的算法。这是因为我们的算法非常简单,我们的算法可以用来执行,而运行时间是用来把最佳的比标准法返回任何比最优的自动的方法。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2021年4月2日
最新《图理论》笔记书,98页pdf
专知会员服务
74+阅读 · 2020年12月27日
《常微分方程》笔记,419页pdf
专知会员服务
71+阅读 · 2020年8月2日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
专知会员服务
159+阅读 · 2020年1月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年12月31日
Arxiv
0+阅读 · 2021年12月31日
Arxiv
0+阅读 · 2021年12月29日
Arxiv
0+阅读 · 2021年12月29日
Arxiv
7+阅读 · 2019年5月31日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
相关资讯
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年12月31日
Arxiv
0+阅读 · 2021年12月31日
Arxiv
0+阅读 · 2021年12月29日
Arxiv
0+阅读 · 2021年12月29日
Arxiv
7+阅读 · 2019年5月31日
Arxiv
3+阅读 · 2017年12月1日
Top
微信扫码咨询专知VIP会员