Memaksimalkan bobot jumlah ujung

Saya ingin tahu apakah masalah berikut memiliki nama, atau hasil apa pun yang terkait dengannya.

Misalkan adalah grafik berbobot di mana menunjukkan bobot tepi antara dan , dan untuk semua , . Masalahnya adalah untuk menemukan subset dari simpul yang memaksimalkan jumlah dari bobot tepi yang berdekatan dengan mereka: Perhatikan bahwa saya menghitung sisi yang berada di dalam subset dan yang berada di luar subset, yang membedakan masalah ini dari max-cut. Namun, meskipun dan berada di , saya hanya ingin menghitung edge $G = (V,w)$ $w(u,v)$ $u$ $v$ $u,v \in V$ $w(u,v) \in [-1,1]$

max_{S \subseteq V} \sum_{(u, v) : u \in S or v \in S} w (u, v)

$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$

u

$u$

v

$v$

S

$S$

(u, v)

$(u,v)$ sekali (bukan dua kali), yang membedakan tujuan dari sekedar jumlah derajat.

Perhatikan bahwa masalahnya sepele jika semua bobot tepi adalah non-negatif - cukup ambil seluruh grafik!

reference-request graph-theory approximation-algorithms terminology approximation-hardness Aaron Roth
sumber

Definisi Anda tidak cocok dengan catatan Anda nanti tentang tidak menghitung sisi duplikat. Apakah Anda menjumlahkan pasangan yang dipesan atau 2 elemen elemen? (Yang terakhir akan memberi Anda properti yang Anda butuhkan, saya pikir)

Suresh Venkat

Catatan lain: satu-satunya bobot tepi yang tidak dihitung adalah yang berada di dalam V \ S. .

Suresh Venkat

@ Suresh: Definisi formal dalam pertanyaan sudah benar selama rasio perkiraan terkait. Itu hanya memberikan persis dua kali dari apa yang diharapkan seseorang dari kata-kata.

Tsuyoshi Ito

@ TsuyoshiIto: oh begitu, karena ujung-ujungnya juga dihitung dua kali.

Suresh Venkat

Masalah sebenarnya adalah NP-hard karena, seperti yang ditulis Suresh dalam komentarnya, masalahnya setara dengan pemrograman kuadratik {0,1} yang tidak dibatasi, yaitu NP-hard.

Tsuyoshi Ito

Jawaban:

Bukan benar-benar solusi tetapi beberapa pengamatan.

Ini adalah kasus khusus dari masalah berikut: diberikan semesta , dan kumpulan set , dan fungsi bobot , temukan himpunan sedemikian rupa sehingga dimaksimalkan (bobot himpunan adalah berat total unsur-unsurnya). Masalah Anda sesuai dengan kasus di mana setiap elemen muncul tepat dalam dua set (tapi saya tidak yakin bagaimana memanfaatkan pembatasan ini, meskipun mungkin membantu). $U = \{1, \ldots, m\}$ $S_1, \ldots, S_n \subseteq U$ $w:U \rightarrow [-1, 1]$ $I \subseteq [n]$ $w(\bigcup_{i \in I}{S_i})$ $U$

Ini adalah masalah cakupan: mirip dengan Max-k-Set-Cover, tetapi tanpa batasan untuk menggunakan set dan dengan bobot negatif diizinkan. Aproksimasi serakah dari Max-k-Set-Cover (pada setiap langkah menghasilkan set yang memiliki berat terbesar elemen yang belum ditemukan sejauh ini) menampilkan urutan set sehingga set pertama adalah perkiraan terhadap optimal (jadi ini adalah pendekatan simultan untuk semua ). Sayangnya, seperti biasa, ada masalah dengan menganalisanya ketika bobot bisa negatif. Pengamatan dasar dari analisis algoritma serakah adalah bahwa jika adalah set pertama yang merupakan output, maka ( $k$ $k$ $1 + 1/e$ $k$ $S_1$ $w(S_1) \geq OPT_k/k$ $OPT_k$ menjadi bobot maksimum yang dicakup oleh set), karena kurang dari jumlah bobot set dalam solusi optimal, dan masing-masing memiliki bobot kurang dari . Namun, dengan bobot negatif tidak lagi benar bahwa kurang dari jumlah bobot dalam solusi optimal. Secara umum, ikatan serikat tidak lagi benar. $k$ $OPT_k$ $k$ $w(S_1)$ $OPT_k$

Sasho Nikolov
sumber

FWIW, masalah Anda sulit diperkirakan dalam faktor multiplikasi untuk . $n^{1-\epsilon}$ $\epsilon>0$

Kami menunjukkan bahwa di bawah ini dengan memberikan pengurangan melestarikan aproksimasi dari Independent Set, yang dikenal dengan kekerasan aproksimasi.

Pengurangan dari Set Independen

Biarkan grafik yang tidak diarahkan menjadi turunan dari Set Independen. Biarkan masing menunjukkan tingkat simpul di . Biarkan adalah jumlah simpul di . $G=(V,E)$ $d_v$ $v$ $G$ $n$ $G$

Buatlah graf berbobot tepi dari sebagai berikut. Berikan setiap tepi dalam bobot 1. Untuk setiap simpul non-terisolasi , tambahkan tepi baru, masing-masing dengan bobot , ke simpul baru. Untuk setiap simpul terisolasi , tambahkan satu tepi baru bobot 1 ke simpul baru. $G'=(V',E')$ $G$ $E$ $v\in V$ $d_v-1$ $-1$ $d_v-1$ $v\in V$

(Catatan: setiap simpul baru (dalam tetapi bukan ) memiliki tepat satu tetangga, yaitu dalam ) $G'$ $G$ $G$

Kata pengantar singkat. memiliki seperangkat ukuran independen iff (sebagai contoh masalah Anda) memiliki solusi nilai setidaknya . $G$ $k$ $G'$ $k$

Bukti. Biarkan menjadi setiap set independen dalam . Kemudian, karena simpul dalam adalah independen dalam , nilai dalam (menurut tujuan Anda) adalah $S$ $G$ $S$ $G'$ $S$ $G'$

\sum_{v \in S} d_{v} - (d_{v} - 1) = | S | .

$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$

Sebaliknya, biarkan menjadi solusi untuk dari nilai setidaknya . Tanpa kehilangan keumuman, anggap tidak mengandung simpul baru. (Setiap simpul baru berada di satu sisi . Jika tidak diisolasi dalam , maka bobot tepi adalah , jadi menghapus dari meningkatkan nilai Jika diisolasi, maka berat tepi adalah 1, jadi menghapus dari dan menambahkan mempertahankan nilai ) $S$ $G'$ $k$ $S$ $v'$ $(v',v)$ $v$ $G$ $-1$ $v'$ $S$ $S$ $v$ $v'$ $S$ $v$ $S$

Tanpa kehilangan umum, menganggap bahwa adalah himpunan bebas di . (Kalau tidak, biarkan menjadi tepi sehingga dan berada di Berat total tepi insiden di adalah , sehingga total berat Tepi insiden selain dari paling banyak nol. Dengan demikian, menghapus dari tidak akan meningkatkan nilai ) $S$ $G$ $(u,v)$ $u$ $v$ $S$ $v$ $G'$ $d_v - (d_v-1) = 1$ $v$ $(u,v)$ $v$ $S$ $S$

Sekarang, dengan perhitungan yang sama seperti pada awal pembuktian, nilai adalah. Oleh karena itu . QED $S$ $|S|$ $|S| \ge k$

Sebagai tambahan, Anda dapat meminta perkiraan aditif , dari, katakanlah, atau . $O(n)$ $\epsilon m$

Tampaknya mungkin bagi saya bahwa untuk masalah Anda bahkan memutuskan apakah ada solusi bernilai positif bisa NP-keras.

Neal Young
sumber