Re: Linear Program Optimal Extreme Points

Hi,

El vie, 07-10-2022 a las 11:04 +1030, Prabhu Manyem escribi=C3=B3:
> To Andrew, Peter and Manuel,
>=20
> Thank you for your help on this topic.
>=20
> To Manuel, Why only vertices next to the starting vertex?=C2=A0 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 th=
e one in the book.

But from the practical view point I think the problem will be intractable v=
ery soon.

Regards, Manuel

>=20
> But in the example that you gave, I can walk directly from BR (bottom
> right) to TR (top right), or from TL to TR.
>=20
> 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.
>=20
> Best,
> -Prabhu
>=20