Algoritma Max-Cut yang seharusnya tidak berfungsi, tidak jelas mengapa

Oke, ini mungkin tampak seperti pertanyaan pekerjaan rumah dan, dalam arti tertentu, itu benar. Sebagai tugas rumah di kelas algoritma sarjana, saya memberikan klasik berikut:

Diberikan grafik tak berarah , berikan algoritma yang menemukan potongan sedemikian rupa sehingga , di mana adalah jumlah sisi yang memotong potongan. Kompleksitas waktu harus .( S , ˉ S ) δ ( S , ˉ S ) ≥ | E | / 2 δ ( S , ˉ S ) O ( V + E $G=(V,E)$$(S,\bar{S})$$\delta(S,\bar{S})\geq |E|/2$$\delta(S,\bar{S})$$O(V+E)$

Untuk beberapa alasan, saya mendapat banyak solusi berikut. Sekarang, ini memang menggunakan terlalu banyak waktu, jadi ini bukan masalah penilaian, tapi saya ingin tahu. "Kelihatannya" tidak benar, tetapi semua upaya saya pada contoh tandingan gagal. Ini dia:

1. Setel$S\leftarrow \emptyset$
2. Biarkan menjadi simpul derajat maks dalam grafik$v$
3. Tambahkan ke$v$$S$
4. Hapus semua tepi yang berdekatan dengan$v$
5. Jika kembali ke 2$\delta(S,\bar{S}) < |E|/2$

Perhatikan bahwa dalam langkah 5 mengacu pada grafik asli. Perhatikan juga bahwa jika kita melewatkan langkah 4, ini jelas akan salah (misalnya penyatuan segitiga dengan dua sisi yang terisolasi).$E$

Sekarang, setiap bukti sederhana memiliki masalah berikut - mungkin ketika kita menambahkan titik kita benar-benar menghapustepi dari potongan sambil menambahkan tepi baru (di mana mengacu pada grafik dengan tepi dihapus. Masalahnya adalah, bahwa jika ini merugikan tujuan kita, itu berarti bahwa "dulu" memiliki tingkat yang lebih tinggi, jadi "seharusnya" dipilih sebelumnya.$v$$|S|$$d(v)$$d(v)$$v$

Apakah ini algoritma yang terkenal? Apakah ada contoh tandingan sederhana untuk itu?

^{Klaim saya sebelumnya dari tidak memperhitungkan potongan ukuran sudah ada dalam grafik. Konstruksi berikut ini muncul sebagai hasil (secara empiris - Saya telah membuat pertanyaan di math.stackexchange.com untuk bukti yang kuat) dalam fraksi . n2/4O($\frac{2}{c+6}$$n^2/4$$O\left(\frac{1}{\log c}\right)$}

Algoritme berkinerja buruk di serikat beberapa grafik lengkap, ukuran terputus berbeda. Kami menunjukkan grafik lengkap pada simpul sebagai . Pertimbangkan perilaku algoritma pada : itu berulang kali menambahkan titik sembarang belum dalam ke - semua simpul tersebut adalah identik dan jadi urutannya tidak masalah. Mengatur jumlah simpul yang belum ditambahkan ke oleh algoritma , ukuran potongan pada saat itu adalah .K n K n S S S | ˉ S | = k k ( n - k $n$$K_n$$K_n$$S$$S$$S$$|\bar{S}| = k$$k (n-k)$

Pertimbangkan apa yang terjadi jika kita menjalankan algoritma pada beberapa grafik terputus dengan konstanta antara 0 dan 1. Jika adalah jumlah elemen yang belum dalam dalam grafik lengkap ke- , maka algoritma tersebut akan berulang kali menambahkan sebuah simpul ke dari grafik lengkap dengan tertinggi , memutus ikatan secara sewenang-wenang. Ini akan menginduksi penambahan simpul berbasis `bulat 'ke : algoritme menambahkan simpul dari semua grafik lengkap dengan tertinggi , kemudian dari semua grafik lengkap dengan (dengan x i k i S i S k i S k = k i k i = k - 1 k i$K_{x_i n}$$x_i$$k_i$$S$$i$$S$$k_i$$S$$k = k_i$$k_i=k-1$$k_i$diperbarui setelah ronde sebelumnya), dan seterusnya. Setelah grafik lengkap memiliki simpul yang ditambahkan ke dalam satu putaran, itu akan melakukannya untuk setiap putaran sejak saat itu.$S$

Biarkan menjadi jumlah grafik lengkap. Biarkan dengan menjadi pengubah ukuran untuk grafik lengkap ke- . Kami memesan pengubah ukuran ini dari besar ke kecil dan mengatur . Kita sekarang memiliki bahwa jika ada grafik dengan elemen persis belum ditambahkan ke , maka ukuran pemotongan pada waktu itu adalah . Jumlah total tepi adalah .0 < x i ≤ 1 0 ≤ i ≤ c - 1 i x 0 = 1 c ′ k S ¢ c ′ - 1 i = 0 k ( x i n - k ) = k n ≤ c ′ - 1 i = 0 ( x i ) - c ′ k 2 | $c$$0 < x_i \leq 1$$0 \leq i \leq c - 1$$i$$x_0 = 1$$c'$$k$$S$$\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$$|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$

Perhatikan bahwa adalah fungsi kuadratik dalam dan karenanya memiliki maksimum. Karena itu kami akan memiliki beberapa pemotongan maksimal secara lokal. Misalnya, jika potongan maksimal kami adalah pada dengan ukuran . Kita akan memilih sehingga , yang berarti grafik lengkap kedua tidak akan mengubah ukuran pemotongan maksimal lokal ini di . Kami kemudian mendapatkan potongan maksimal lokal baru di dan jadi kami memilih (dengan k c = 1 k = $k n \sum_{i=0}^{c'-1} x_i - c' k^2$$k$$c=1$ n$k=\frac{n}{2}$ x1x1=1/2-εk=$\frac{n^2}{4}$$x_1$$x_1 = 1/2 - \varepsilon$ k=3/8n-ε'x2=3/8n-ε"ε,ε',ε"εx1=1/2x1n=$k=\frac{n}{2}$$k=3/8 n - \varepsilon'$$x_2 = 3/8 n - \varepsilon''$$\varepsilon, \varepsilon', \varepsilon''$konstanta kecil). Kami akan mengabaikan s untuk saat ini dan anggap saja kami dapat memilih - kami harus memastikan , tetapi ini tidak akan mempengaruhi hasil akhir jika adalah cukup besar.$\varepsilon$$x_1 = 1/2$$x_1 n = \frac{n}{2} - 1$$n$

Kami ingin menemukan maksimum lokal dari pemotongan kami. Kami membedakan hingga , menghasilkan . Menyamakan dengan menghasilkan , yang memberikan potongan ukuran . k n ∑ c ′ - 1 i = 0 ( x i ) - 2 c ′ k 0 k = $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$$k$$n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$$0$n$k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$

Biarkan menjadi ditentukan dalam paragraf sebelumnya jika . Kami akan memastikan bahwa formula berlaku dengan menuntut bahwa - semua grafik lengkap dengan kemudian lebih kecil daripada dari potongan maksimum lokal ini dan karenanya tidak menambah ukuran potongan. Ini berarti kami memiliki potongan pada ini yang lebih besar dari semua potongan lain yang ditemukan oleh algoritma. k c ′ = i x i n < k i i ′ i ′ > i k i c k $k_i$$k$$c'=i$$x_i n < k_i$$i'$$i'>i$$k_i$$c$$k_i$

Mengisi , kita mendapatkan perulangan (ditambah beberapa kecil ) dengan . Memecahkan hasil ini : lihat pertanyaan saya di math.stackexchange.com untuk derivasi oleh @Daniel Fisher. Memasukkan ini ke dan menggunakan wawasan kita tentang perulangan memberi kita potongan ukuran . Menggunakan properti dari koefisien binomial pusat ini , kami milikix i = $x_i n < k_i$εx0=1xi= ( 2 $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$$\varepsilon$$x_0 = 1$ n$x_i = \frac{\binom{2i}{i}}{4^i}$n$\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$limc′→∞c′( ( 2 c $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$$\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (juga lihat pertanyaan saya di math.stackexchange.com ).

Jumlah tepi kira-kira . Berdasarkan properti yang dikenal, kita memiliki . Pengarsipan memberikan setidaknya yang asimptotik ketika pergi ke tak terbatas.$\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$ n$\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$ n$\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$$\frac{n^2}{8} \log c$$c$

Karenanya, kami memiliki secara asimptotik sama dengan saat berjalan hingga tak terbatas, menunjukkan bahwa algoritme dapat potongan kembali yang merupakan fraksi rendah sewenang-wenang dari.$\frac{\delta(S, \bar{S})}{|E|}$ c| E$\frac{8}{\pi \log c}$$c$$|E|$

Setelah beberapa saat berpikir dan bertanya-tanya, inilah contoh tandingan, dari Ami Paz :

Biarkan menjadi genap dan menjadi grafik yang merupakan gabungan dari dengan pencocokan simpul (yaitu pencocokan dengan tepi ).G K n n + 2 n / 2 + $n$$G$$K_n$$n+2$$n/2+1$

Bagaimana algoritme berjalan pada grafik ini? Hanya perlu simpul dari bagian klik dalam urutan acak. Setelah mengambil dari clique, potongannya berukuran . Ini maksimal untuk , yang memberikan potongan ukuran , sedangkan jumlah tepi dalam grafik adalah .k ⋅ ( n - k ) k = n / 2 n $k$$k\cdot (n-k)$$k=n/2$ n$\frac{n^2}{4}$$\frac{n^2}{2}+1$

Algoritme seperti yang ditentukan akan terus menambahkan simpul dari klik, mengurangi jumlah tepi melintasi memotong, sampai apa yang tersisa dari klik hanya satu sisi. Pada titik ini ia tidak dapat memperoleh yang lebih baik dari .$\frac{n}{2}+2$