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
Hi,
A finite dimensional polyhedron could have exponentially many vertices!
For an all-zero objective function - in case when the LP problem turns
to a feasibility problem: no one can check nor list all the vertices in
polynomial time = no polynomial size witness, can't be NP-complete!
Even
Hi, Andrew:
I don't kown if it is implemented somewhere. But the problem of generating all
the optimal vertices is the same as generating all the
vertices of a new polyhedron in 1 lower dimension.
But that problem is known to be NP-complete [1], so it is very hard or almost
impossible as soon
Forwarded Message
From: Prabhu Manyem
To: fuk...@math.ethz.ch, Andrew Makhorin , avis@cs.mcgill.c
a
Subject: Linear Program Optimal Extreme Points
Date: Thu, 6 Oct 2022 10:04:22 +1030
Dear Andrew, Komei, David,
I am a retired Maths professor in Adelaide, Australia.
About the
