Wednesday, September 21, 2005

Schrijver's book, Tardos result, and {0,+1,-1} matrices

Schrijver's book has a chapter 15 which is titled Further polynomiality results in linear programming. In that chapter, he covers some additional methods of solution -- as opposed to well known results by Khachiyan, Karmarkar and others -- to the LP problem. The additional results being Megiddo's result, Tardos result. My post on Megiddo's result is this. The result by by Tardos (corollary 15.3a of the book) is significant as it gives a characterization of {0,+1,-1} matrices. It is in pages 195-199 of Schrijver's book. Also, Megiddo's result follows in pages 199-204. The following is the statement we are interested in:

Corollary 15.3a: Tardos result states that there exists a strongly polynomial time algorithm for rational LP problems with {0,+1,-1} constraint matrix.
Intuition: The intuition for this corollary is pretty clear: Khachiyan's method is a polynomial time algorithm, but not strictly polynomial time algorithm. The running time of Khachiyan's algorithm -- for a problem of the type Ax <= b -- is dependent on not just the size of the matrix A, meaning the number of rows and columns of A, but also the number of bits used in encoding the matrix A. OTOH, when we restrict the matrix A to be a {0,+1,-1} matrix, which means we are operating in the unary mode, Khachiyan's algorithm takes strictly polynomial time.

The other contribution of Tardos is that the running time of Khachiyan's algorithm takes time independent of either the size of b or the number of bits used in encoding b. This is as important contribution, as we can reduce the problem complexity to that of a homogeneous system.

Look up if Schrijver's new book has any more information on the same.
What does Schrijver's books says about hypergraphs??

Schrijver's new book also has lot of information on these questions. esp. in chapters 21,24 etc.

Are we searching for multi commodity flows?

No comments: