Penguatan submodularity

13

Fungsi-set adalah submodular monoton jika untuk semua , $f$ $A,B$

f (SEBUAH) + f (B) \geq f (SEBUAH \cup B) + f (SEBUAH \cap B) .

$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$

Properti yang lebih kuat adalah

\begin{matrix} f (SEBUAH) + f (B) + f (C) + f (SEBUAH \cup B \cup C) \geq \\ f (SEBUAH \cup B) + f (B \cup C) + f (SEBUAH \cup C) + f (SEBUAH \cap B \cap C) . \end{matrix}

$\begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$ Mengambil

C = A \cup B

$C = A\cup B$ , properti ini menyiratkan submodularity monoton.

Apakah properti ini dikenal?

Latar Belakang

Properti ini muncul ketika mencoba untuk mengkarakterisasi fungsi cakupan. Mengingat beberapa alam semesta tertimbang $U$ (semua berat non-negatif) dan keluarga $X$ dari himpunan bagian dari $U$ , fungsi cakupan $f(S)$ didefinisikan untuk $S \subseteq X$ sebagai berat total unsur ditutupi oleh set di $S$ . Fungsi $f$ selalu monoton dan submodular. Kebalikannya tidak benar.

Properti yang dimaksud menyiratkan bahwa $f$ adalah fungsi cakupan dalam kasus $|X| = 3$ . Serupa, properti yang lebih rumit bekerja untuk lebih besar $X$ . Semua properti ini dipenuhi oleh fungsi cakupan, jadi ini adalah karakterisasi lengkap.

ds.algorithms approximation-algorithms submodularity Yuval Filmus
sumber

13

$k^{th}$

Fungsi peningkatan monoton jika dan hanya jika turunan diskrit orde pertama adalah + ve. yaitu ketika . $f(B)-f(A)\ge 0$ $A\subseteq B$

Submodularity jika dan hanya jika turunan diskrit urutan kedua adalah -ve. yaitu . $(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$

Demikian pula jika Anda memiliki kondisi pada turunan berikutnya Anda mendapatkan fungsi cakupan. (Saya pikir tanda-tanda harus + ve untuk bahkan turunan pesanan dan -ve untuk turunan pesanan aneh) $n$

Sesuatu yang serupa sudah diketahui dalam probabilitas. Fungsi cakupan juga dapat dianggap sebagai ukuran probabilitas (hingga konstanta penskalaan). Satu-satunya referensi yang bisa saya gali adalah halaman 439 dari buku Feller tentang kemungkinan.

Ashwinkumar BV
sumber

Terima kasih untuk referensi! Kondisi turunan diskrit sedikit berbeda, karena Anda hanya mempertimbangkan untuk menambahkan satu elemen pada satu waktu. Monotonitas agaknya adalah dan submodularitas adalah . Yang terakhir ini sebenarnya setara dengan kondisi biasa hanya ketika tidak ada adalah bagian dari yang lain. Jadi properti urutan ketiga saya (yang membutuhkan yang sebelumnya secara umum penuh) tidak muncul di koran.

f (A \cup {x}) \geq f (A)

$f(A \cup \{x\}) \geq f(A)$

f (A \cup {x}) + f (A \cup {y}) \geq f (A \cup {x, y}) + f (A)

$f(A \cup \{x\}) + f(A \cup \{y\}) \geq f(A \cup \{x,y\}) + f(A)$

A, B

$A,B$

Yuval Filmus

7

\begin{matrix} f (SEBUAH \cap B) + f (SEBUAH \cap C) + f (B \cap C) + f ((SEBUAH \cap B) \cup (SEBUAH \cap C) \cup (B \cap C)) \geq \\ f (SEBUAH \cap (B \cup C)) + f (B \cap (SEBUAH \cup C)) + f (C \cap (SEBUAH \cup B)) + f (SEBUAH \cap B \cap C) . \end{matrix}

$\begin{multline*} f(A \cap B) + f(A \cap C) + f(B \cap C) + f((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\ f(A \cap (B \cup C)) + f(B \cap (A \cup C)) + f(C \cap (A \cup B)) + f(A \cap B \cap C). \end{multline*}$ Kondisi "agregat" disebutkan dalam makalah "Karakterisasi kerucut fungsi pseudo-boolean melalui ketidaksetaraan tipe supermodularity" oleh Cramma, Hammer dan Holtzman (ketidaksetaraan (4)), yang merupakan bagian dari koleksi langka "Metode Kuantitatif dalam den Wirtschaftswissenschaften ". Kondisi ini harus sama dengan kondisi saya.

\begin{matrix} f (SEBUAH) + f (B) + f (C) + f (SEBUAH \cap B \cap C) \geq \\ f (SEBUAH \cup B \cup C) + f (SEBUAH \cap B) + f (SEBUAH \cap C) + f (B \cap C) . \end{matrix}

$\begin{multline*} f(A) + f(B) + f(C) + f(A \cap B \cap C) \geq \\ f(A \cup B \cup C) + f(A \cap B) + f(A \cap C) + f(B \cap C). \end{multline*}$

C = \emptyset

$C = \varnothing$

Yuval Filmus
sumber

Penguatan submodularity

Latar Belakang

Jawaban: