Menemukan bidang pemotongan yang membagi polihedron secara merata

Katakanlah kita memiliki polyhedron dalam bentuk standar:

\begin{aligned} SEBUAH 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*}$

Adakah metode yang diketahui untuk menemukan hyperplane yang membagi polyhedron sedemikian rupa sehingga jumlah simpul di setiap sisi hyperplane kira-kira sama? (Yaitu algoritma yang meminimalkan perbedaan absolut kardinalitas verteks pada dua sisi split). $\mathbf{d} \mathbf{x} +d_0= 0$

Juga, apakah ada hasil yang diketahui mengenai kompleksitas masalah ini?

Tambahan: Membatasi jenis pemotongan:

Berikut adalah variasi dari masalah asli dengan harapan lebih mudah diselesaikan daripada yang asli:

Apakah ada cara untuk menghitung atau memperkirakan secara efisien yang mengkoordinasikan hyperplane dari bentuk akan menghasilkan perbedaan absolut terendah kardinalitas vertex di kedua sisi split? Dengan efisien, saya maksudkan sesuatu yang lebih efisien daripada enumerasi lengkap kardinalitas verteks untuk semua kemungkinan perpecahan tersebut. $i$ $d_ix_i + d_0 = 0$

Catatan: Setelah beberapa hari mengalami sedikit kemajuan, saya juga memposting pertanyaan ini di MathOverflow .

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

Tidakkah orang bisa membuktikan ini masalah NP-hard?

Peter Shor

Terima kasih @Peter. Sebuah bukti akan sangat bagus. Yang mengatakan, saya menganggap masalahnya sulit, dan saya pikir saya lebih tertarik pada heuristik atau algoritma perkiraan. Motivasi di balik gagasan membatasi jenis pemotongan sebagian untuk melihat apakah ada variasi yang lebih mudah dari masalah umum yang kita sudah tahu solusi atau algoritma perkiraan.

Amelio Vazquez-Reina

Bagaimana dengan sesuatu di sepanjang garis ini (tidak yakin apakah itu berfungsi) - Kita tahu menghitung jumlah pencocokan bipartit maksimum adalah # P-hard. Kita juga tahu bahwa program linier untuk menemukan pencocokan bipartit maksimum benar-benar unimodular dan dengan demikian setiap titik sudut / solusi layak dasar adalah integral. Untuk masalah pencocokan bipartit maksimum, cari nilai pencocokan. Bangun program linier dengan batasan bahwa setiap solusi harus memiliki nilai optimal. Maka setiap titik sudut cocok. Mampu membagi berulang kali secara merata berarti Anda harus dapat menghitung jumlah pertandingan.

Memilih

Sudahlah. Kita juga harus bisa menghitung jumlah simpul yang ditambahkan oleh bidang pemotongan.

Memilih

Menemukan bidang pemotongan yang membagi polihedron secara merata

Tambahan: Membatasi jenis pemotongan:

Jawaban: