Dual consistent systems of linear inequalities and cardinality constrained polytopes
Dual consistent systems of linear inequalities and cardinality constrained polytopes
复制标题
线性不等式和基数约束多面体的双一致系统
DOI：
10.1007/s10107-014-0748-2
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Fujishige and J. Massberg
中科院分区：
文献类型：
--
作者：
Yue Wang;Masaki Nakano;Satoshi Yoshida;Mohammad Saeed Bahramy;Hideki Matsuoka;Yuki Majima;Yuta Ohigashi;Yuta Kashiwabara;Masato Sakano;Kyoko Ishizaka;Yoshihiro Iwasa;S. Fujishige and J. Massberg
本文引入了线性不等式组的对偶相容性的概念，具有充分的一般性。我们证明了基数约束的多面体由一定的线性不等式系统表示当且仅当与基数相关的线性不等式系统是对偶相容的。典型的对偶相容不等式组是描述具有一定选择函数的多拟阵、广义多拟阵和对偶贪婪多面体的不等式组。我们证明了基数约束的普通二部匹配多面体的不等式系统一般不是对偶相容的，并给出了使其对偶相容的附加不等式。此外，我们表明，普通系统的基数约束（多）拟阵相交的不等式不是对偶一致的，这反驳了一个猜想的Maurras，Spiegelberg，和Stephan的基数约束的多拟阵相交的线性表示。
We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the systems of inequalities for cardinality-constrained ordinary bipartite matching polytopes are not dual consistent in general, and give additional inequalities to make them dual consistent. Moreover, we show that ordinary systems of inequalities for the cardinality-constrained (poly)matroid intersection are not dual consistent, which disproves a conjecture of Maurras, Spiegelberg, and Stephan about a linear representation of the cardinality-constrained polymatroid intersection.
登录
查看更多内容
单位超立方体中对偶多面体的一个例子
DOI：
10.1016/s0167-5060(08)70746-5
发表时间：
1977
期刊：
Annals of discrete mathematics
影响因子：
--
作者：
J. Maurras
通讯作者：
J. Maurras
影响因子：
4.9
作者：
Santos, Francisco
通讯作者：
Santos, Francisco
关于基数约束拟阵多胞形
影响因子：
2.1
作者：
J. Maurras;Rüdiger Stephan
通讯作者：
Rüdiger Stephan
基数齐次集合系统、拟阵中的循环以及相关的多面体
DOI：
10.1137/1.9780898718805.ch8
发表时间：
2004
期刊：
--
影响因子：
--
作者：
M. Grötschel
通讯作者：
M. Grötschel