Say we have a convex polytope in standard form:
\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}
Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same? (i.e. a hyperplane that minimizes the absolute difference of vertex cardinalities on the two sides of the split).
Also, are there any known results regarding the computational complexity of this problem?
Addendum: Restricting the types of cuts:
Here is a variation of the original problem with the hope that it is easier to solve than the original one:
Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all such possible splits.
Note:
I first asked this question in CSTheory.stackexchange.com last week. Since the question has not seen any significant progress since then, I thought I could try here.