An analog of the Cook theorem for polytopes

DOI10.3103/S1066369X1208004XzbMath1262.90149MaRDI QIDQ1759309

Aleksandr N. Maksimenko

Publication date: 20 November 2012

Published in: Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

cut polytopefacetspolynomial reducibility of problemspolytope of the knapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Boolean quadric polytopes are faces of linear ordering polytopes, Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

Cites Work

• Expressing combinatorial optimization problems by linear programs
• All 0-1 polytopes are traveling salesman polytopes
• Facets of the linear ordering polytope
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
• Geometry of cuts and metrics
• Unnamed Item
• Unnamed Item