Re: Linear Program Optimal Extreme Points

[Manuel Muñoz Márquez]

Hi,

El vie, 07-10-2022 a las 11:04 +1030, Prabhu Manyem escribió:
> To Andrew, Peter and Manuel,
> 
> Thank you for your help on this topic.
> 
> To Manuel, Why only vertices next to the starting vertex?  If the
> links are A-->B-->C and B-->D, so first you go from A to B, then B to
> C, then backtrack to B (from C), and then you can go from B to D...
> This is what I had in mind when I said "traverse in a tree-like
> fashion".. (But yes, to do backtracking, you should store the Bases of
> A and B in memory).

You are wright, I miss the second and successive iteration.

My first impression is that the procedure you propose is not the same as the 
one in the book.

But from the practical view point I think the problem will be intractable very 
soon.

Regards, Manuel

> 
> But in the example that you gave, I can walk directly from BR (bottom
> right) to TR (top right), or from TL to TR.
> 
> To Peter-- Yes, they can have exponentially many vertices.. But I
> think there are "doubly polynomial" algorithms that can do
> enumeration.. Doubly Polynomial means, polynomial in the size of the
> input+output.. Here is one reference:
> https://www.research-collection.ethz.ch/handle/20.500.11850/426218
> (Chapter 8, I think).. I came to know about this only recently.
> 
> Best,
> -Prabhu
>