Forbidden Vertices
Forbidden Vertices
复制标题
禁止顶点
DOI：
--
复制
发表时间：
2013
影响因子：
1.7
通讯作者：
V. Kaibel
中科院分区：
文献类型：
--
作者：
Gustavo Angulo;Shabbir Ahmed;Santanu S. Dey;V. Kaibel
在这项工作中，我们介绍和研究禁止顶点问题。给定一个多胞形P及其顶点子集X，研究P的顶点子集不包含在X中的线性优化问题的复杂性。这个问题与寻找线性问题的k-最佳基本解密切相关。我们表明，问题的复杂性变化显着取决于P和X的编码。我们提供额外的易处理性结果和扩展配方时，P只有二进制顶点。讨论了整多面体的一些应用和推广。
In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X . This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X . We provide additional tractability results and extended formulations when P has binary vertices only. Some applications and extensions to integral polytopes are discussed.