Encontrar un plano de corte que divida uniformemente un poliedro

Digamos que tenemos un poliedro en forma estándar:

\begin{aligned} UNA X = si \\ X \geq 0 0 \end{aligned}

$\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}$

¿Hay algún método conocido para encontrar un hiperplano que divide el poliedro de manera que el número de vértices en cada lado del hiperplano es aproximadamente el mismo? (es decir, un algoritmo que minimiza la diferencia absoluta de cardinalidades de vértice en los dos lados de la división). $\mathbf{d} \mathbf{x} +d_0= 0$

Además, ¿hay algún resultado conocido con respecto a la complejidad de este problema?

Anexo: Restricción de los tipos de cortes:

Aquí hay una variación del problema original con la esperanza de que sea más fácil de resolver que el original:

¿Hay alguna manera de calcular o estimar eficientemente para qué coordenada un hiperplano de la forma produciría la diferencia absoluta más baja de cardinalidades de vértice en ambos lados de la división? Por eficiente quiero decir algo más eficiente que la enumeración exhaustiva de cardinalidades de vértice para todas estas divisiones posibles. $i$ $d_ix_i + d_0 = 0$

Nota: Después de unos días de poco progreso, publiqué esta pregunta también en MathOverflow .

ds.algorithms linear-programming linear-algebra Amelio Vazquez-Reina
fuente

¿No debería uno ser capaz de demostrar que este es un problema NP-difícil?

Peter Shor

Gracias @Peter. Una prueba sería genial. Dicho esto, supongo que el problema es difícil, y creo que estoy más interesado en los algoritmos de heurística o aproximación. La motivación detrás de la idea de restringir los tipos de cortes fue en parte para ver si hay variaciones más fáciles del problema general para el que ya conocemos una solución o un algoritmo de aproximación.

Amelio Vazquez-Reina

¿Qué tal algo a lo largo de estas líneas (no estoy seguro si funciona)? Sabemos que contar el número máximo de coincidencias bipartitas es # P-difícil. También sabemos que un programa lineal para encontrar una coincidencia bipartita máxima es totalmente unimodular y, por lo tanto, cualquier punto de esquina / solución factible básica es integral. Para un problema de coincidencia bipartita máxima, encuentre el valor de la coincidencia. Construya un programa lineal con la restricción de que cualquier solución debe tener el valor óptimo. Entonces cada punto de esquina es una coincidencia. Ser capaz de dividir repetidamente en partes iguales significa que debería poder contar la cantidad de coincidencias.

Optar el

No importa. También habría que poder contar la cantidad de vértices añadidos por el plano de corte.

Optar el

Encontrar un plano de corte que divida uniformemente un poliedro

Anexo: Restricción de los tipos de cortes:

Respuestas: