Timeline for Complexity of finding one vertex of a nonempty polytope

8 events

when toggle format	what		by	license	comment
S Jul 31, 2019 at 16:46	history	edited	András Bátkai	CC BY-SA 4.0	added 2 characters in body; edited tags
Jul 31, 2019 at 16:32	review	Suggested edits
S Jul 31, 2019 at 16:46
May 10, 2019 at 10:14	vote	accept	guigux
May 9, 2019 at 15:38	comment	added	Dima Pasechnik		probably it's better to think of shooting at direction of increasing/decreasing a coordinate of $x_0$. So you compute the slacks at $x_0$ - here you need $O(mn)$: if one of them is 0, you got a facet to restrict to. Otherwise, pick an arbitrary coordinate $k$ of $x_0$, and form a univariate system of inequalities involving this coordinate as a variable. Find a vertex solution to it, this is a new value for the $k$-th coordinate of $x_0$, so that it lies on a facet. This can be done in $O(m)$ operations.
May 9, 2019 at 13:41	history	edited	guigux	CC BY-SA 4.0	added 142 characters in body
May 8, 2019 at 21:58	answer	added	Dima Pasechnik		timeline score: 8
May 8, 2019 at 21:25	history	edited	guigux	CC BY-SA 4.0	deleted 6 characters in body
May 8, 2019 at 21:17	history	asked	guigux	CC BY-SA 4.0