The Complexity of Recognizing Facets for the Knapsack Polytope

• 成果类型: Article; Early Access
• 署名作者: Chen, Rui; Zhu, Haoran
• 署名单位: The Chinese University of Hong Kong, Shenzhen; Microsoft
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0481
• 发表日期: 2025-11-17
• 关键词: knapsack polytope; Dp-completeness; parameterized complexity; cutting planes; integer

摘要

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. It was conjectured that recognizing a facet for the knapsack polytope is Dp-complete. 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 coefficients defines a facet of a knapsack polytope.