Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan

Powiedzmy, że mamy wielościan w standardowej formie:

\begin{aligned} ZA x = b \\ x \geq 0 \end{aligned}

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

Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba wierzchołków po każdej stronie hiperpłaszczyzny jest w przybliżeniu taka sama? (tj. algorytm minimalizujący absolutną różnicę liczności wierzchołków po obu stronach podziału). $\mathbf{d} \mathbf{x} +d_0= 0$

Czy są też jakieś znane wyniki dotyczące złożoności tego problemu?

Dodatek: Ograniczanie rodzajów cięć:

Oto wariant pierwotnego problemu z nadzieją, że łatwiej go rozwiązać niż oryginalny:

Czy istnieje sposób na wydajne obliczenie lub oszacowanie, dla której współrzędnej hiperpłaszczyzna w postaci dałaby najniższą bezwzględną różnicę liczności wierzchołków po obu stronach podziału? Przez „efektywny” rozumiem coś bardziej wydajnego niż wyczerpujące wyliczenie liczności wierzchołków dla wszystkich możliwych takich podziałów. $i$ $d_ix_i + d_0 = 0$

Uwaga: po kilku dniach niewielkich postępów opublikowałem to pytanie również w MathOverflow .

ds.algorithms linear-programming linear-algebra Amelio Vazquez-Reina
źródło

Czy nie można udowodnić, że jest to trudny problem związany z NP?

Peter Shor,

Dzięki @Peter. Dowód byłby świetny. To powiedziawszy, zakładam, że problem jest trudny i myślę, że bardziej interesują mnie algorytmy heurystyczne lub aproksymacyjne. Motywem pomysłu ograniczenia rodzajów cięć było po części sprawdzenie, czy istnieją łatwiejsze warianty ogólnego problemu, dla którego znamy już rozwiązanie lub algorytm aproksymacyjny.

Amelio Vazquez-Reina

Co powiesz na coś w tym kierunku (nie jestem pewien, czy to działa) - Wiemy, że policzenie maksymalnej liczby dwustronnych dopasowań to # P-trudne. Wiemy również, że liniowy program znajdujący maksymalne dopasowanie dwustronne jest całkowicie niemodularny, a zatem każde narożne / podstawowe możliwe rozwiązanie jest integralne. W przypadku problemu z maksymalnym dwustronnym dopasowaniem znajdź wartość dopasowania. Skonstruuj program liniowy z takim ograniczeniem, że każde rozwiązanie musi mieć optymalną wartość. Zatem każdy punkt narożny jest dopasowany. Możliwość wielokrotnego dzielenia równomiernie oznacza, że powinieneś być w stanie policzyć liczbę dopasowań.

blokujący

Nieważne. Trzeba też umieć policzyć liczbę wierzchołków dodanych przez płaszczyznę cięcia.

blokujący

Znalezienie płaszczyzny cięcia, która równomiernie dzieli wielościan

Dodatek: Ograniczanie rodzajów cięć:

Odpowiedzi: