论文标题
识别背包多层的方面的复杂性
The Complexity of Recognizing Facets for the Knapsack Polytope
论文作者
论文摘要
复杂性班级DP是所有语言的类别，这些语言是NP中一种语言与Co-NP语言的交集，这是Papadimitriou和Yannakakis（1982）所创造的。 Hartvigsen和Zemel（1992）猜想，识别背包多层的一个方面是DP完整的。尽管众所周知，与其他众所周知的组合优化问题相关的多型相关的方面的识别问题，例如旅行推销员，节点/设定包装/覆盖/覆盖/覆盖，但dp-complete，但这种识别背包多台面方面的猜想仍然打开。我们为这个猜想提供了积极的答案。此外，尽管识别问题存在DP硬度，但我们给出了一种多项式时间算法，以决定是否具有固定数量不同的正系数的不平等，定义了背包多型的方面，从而推广了Balas的结果（1975）。
The complexity class DP is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis (1982). Hartvigsen and Zemel (1992) conjectured that recognizing a facet for the knapsack polytope is DP-complete. While it has been known that the recognition problems of facets for polytopes associated with other well-known combinatorial optimization problems, e.g., traveling salesman, node/set packing/covering, are DP-complete, this conjecture on recognizing facets for the knapsack polytope remains open. We provide a positive answer to this conjecture. Moreover, despite the DP-hardness of the recognition problem, we give a polynomial time algorithm for deciding if an inequality with a fixed number of distinct positive coefficients defines a facet of a knapsack polytope, generalizing a result of Balas (1975).
