The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.


翻译:Nemhauser-Trottter 理论指出,稳定问题的标准线性编程(LP)配方具有显著的属性,也称为(弱的)持久性:对于给某些变量分配整数值的每一种最佳LP解决方案,都存在一种最优的整数解决方案,在这些变量中,这些变量保留相同的数值。虽然标准LP仅由非负数和边际限制来界定,但对其他各种LP配方也进行了研究,人们可能会怀疑其中是否有这种属性。我们表明,任何其他满足温和条件的配方都不可能在所有图表上具有持久性属性,除非它始终与稳定的设定聚苯乙烯相等。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
AI科技评论
4+阅读 · 2018年8月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Arxiv
0+阅读 · 2021年1月10日
Arxiv
0+阅读 · 2021年1月8日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
AI科技评论
4+阅读 · 2018年8月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Top
微信扫码咨询专知VIP会员