This article is cited in 5 papers

An analog of the Cook theorem for polytopes

A. N. Maksimenko

Chair of Discrete Analysis, Yaroslavl State University, Yaroslavl, Russia

Abstract: We prove that the polytope $M$ of any combinatorial optimization problem with a linear objective function is an affine image of a face of the cut polytope whose dimension is polynomial with respect to the dimension of $M$.

Keywords: combinatorial optimization, cut polytope, knapsack polytope, faces, polynomial reducibility of problems.

UDC: 519.854

Received: 28.06.2011

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2012, 56:8, 28–34

Bibliographic databases:

• 
•