Encontrar um plano de corte que divida um poliedro uniformemente

Digamos que temos um poliedro na forma padrão:

\begin{aligned} UMA x = b \\ 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*}$

Existem métodos conhecidos para encontrar um hiperplano que divide o poliedro de uma maneira que o número de vértices em cada lado do hiperplano seja aproximadamente o mesmo? (ou seja, um algoritmo que minimiza a diferença absoluta de cardinalidades de vértices nos dois lados da divisão). $\mathbf{d} \mathbf{x} +d_0= 0$

Além disso, existem resultados conhecidos sobre a complexidade desse problema?

Adendo: Restringindo os tipos de cortes:

Aqui está uma variação do problema original com a esperança de que seja mais fácil resolver do que o original:

Existe uma maneira de calcular ou estimar eficientemente para qual coordenada um hiperplano da forma produziria a menor diferença absoluta de cardinalidades de vértices em ambos os lados da divisão? Por eficiente, quero dizer algo mais eficiente do que a enumeração exaustiva de cardinalidades de vértices para todas essas divisões possíveis. $i$ $d_ix_i + d_0 = 0$

Nota: Após alguns dias de pouco progresso, também postei essa pergunta no MathOverflow .

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

Não se deve provar que esse é um problema difícil de NP?

Peter Shor

Obrigado @Peter. Uma prova seria ótima. Dito isso, presumo que o problema seja difícil e acho que estou mais interessado em heurística ou algoritmos de aproximação. A motivação por trás da idéia de restringir os tipos de cortes foi em parte para verificar se existem variações mais fáceis do problema geral para o qual já conhecemos uma solução ou um algoritmo de aproximação.

Amelio Vazquez-Reina

Que tal algo nesse sentido (não tenho certeza se funciona) - Sabemos que contar o número máximo de correspondências bipartidas é difícil. Também sabemos que um programa linear para encontrar uma correspondência bipartida máxima é totalmente desimodular e, portanto, qualquer ponto de esquina / solução viável básica é parte integrante. Para um problema máximo de correspondência bipartida, encontre o valor da correspondência. Construa um programa linear com a restrição de que qualquer solução precisa ter o valor ideal. Então, cada ponto de canto é uma correspondência. Ser capaz de dividir repetidamente uniformemente significa que você deve poder contar o número de correspondências.

Opte

Deixa pra lá. Também seria necessário contar o número de vértices adicionados pelo plano de corte.

Opte

Encontrar um plano de corte que divida um poliedro uniformemente

Adendo: Restringindo os tipos de cortes:

Respostas: