Three-index linear programs with nested structure

This paper deals with solutions of multi-index linear programs of the transportation type. The approach based on the analysis of reducibility of multi-index transportation problems to flow algorithms is taken as the main technical tool. Sufficient conditions of reducibility are proposed, which are based on the notion of nesting for the set of problem constraints. It is shown that these conditions are necessary and sufficient for reducibility of three-index problems; otherwise, the well-know hypothesis on the non-equivalence of the classes P and NP is wrong.

Presented by the member of Editorial Board: A. A. Lazarev