Given a LP program in standard form, frame a new LP program that has both the primal and dual variables of the original program as its variables. Or, write a LP program whose feasibilty conditions are exactly of those of the original LP program and also of the dual of the original LP program.

--

Schrijver's book says: if the constraint matrix is total-unimodular, then all the points on the surface of the defined polyhedron are integral. This means that the solution is an integer point, not just a rational one. This also corresponds to the set of problems which are in the set NP \cap co-NP. So, a polynomial time algorithm is possible for those problems. (It can also be said that the same is true for all problems in NP, but it means assuming something, which may be possibly presumptous.:)

--

So, given a usual graph theoretic flow problem, which can be formulated as a LP program, do the following to know if the problem is nice:

"reason about the feasibility of the primal and dual and the constraint matrices of both. If they turn out to be total-unimodular, then the program has integer solutions and the problem is in NP \cap co-NP". Then think hard and write a graph theoretic algorithm to solve the problem.

**Note:**in such constraint matrices, we usually deal with the incidence matrix, not the adjacency matrix.

**Question:**We know now know that LP is in P, using any of Khachiyan, Karmarkar, Karp. Then, how much of the above is new?

## No comments:

Post a Comment