An analog of the Cook theorem for polytopes

DOI10.3103/S1066369X1208004XMaRDI QIDQ1759309zbMATH OpenFDO

Authors Aleksandr N. Maksimenko

Publication date 20 November 2012

Published in Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

facetscut polytopepolynomial reducibility of problemspolytope of the knapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 3876926
• Polyhedral combinatorics and combinatorial optimization
• Polyhedral proof methods in combinatorial optimization
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• On the facets of combinatorial polytopes

Cites work

• scientific article; zbMATH DE number 6007904 (Why is no real title available?)
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• All 0-1 polytopes are traveling salesman polytopes
• Computing small clause normal forms
• Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
• Expressing combinatorial optimization problems by linear programs
• Facets of the linear ordering polytope
• Geometry of cuts and metrics

Cited in

(3)

• A theorem on polyhedra which is related to Alexander's separation theorem
• Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes
• Boolean quadric polytopes are faces of linear ordering polytopes

This page was built for publication: An analog of the Cook theorem for polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759309)