Algoritma serakah yang optimal untuk masalah NP-hard

Keserakahan, karena tidak ada kata yang lebih baik, adalah baik. Salah satu paradigma algoritmik pertama yang diajarkan dalam kursus pengantar algoritma adalah pendekatan serakah . Pendekatan serakah menghasilkan algoritma sederhana dan intuitif untuk banyak masalah dalam P. Lebih menarik lagi, untuk beberapa masalah NP-hard, algoritma lokal / lokal yang tamak dan alami menghasilkan (terbukti) faktor perkiraan optimal (di bawah asumsi teoretis kompleksitas yang sesuai). Contoh klasik adalah Set Cover Problem . Algoritma serakah alami memberikan faktor pendekatan O (ln n), yang optimal kecuali P = NP.

Sebutkan beberapa algoritma lokal serakah / lokal untuk masalah NP-hard yang terbukti optimal berdasarkan asumsi teoretis kompleksitas yang sesuai.

Metode ekspektasi bersyarat (untuk derandomisasi algoritma "penugasan acak" untuk Max-Cut dan Max-SAT) dapat dilihat sebagai strategi serakah: untuk , Anda memilih nilai dari variabel x i seperti bahwa jumlah kendala yang diharapkan terpenuhi pada instance tereduksi yang dihasilkan melebihi jumlah kendala yang diharapkan dalam instance saat ini. (Bahkan, algoritma serakah untuk 1 / 2 -approximating Max-Cut adalah sama sebagai "metode harapan bersyarat" algoritma untuk 1 / 2 -approximating Max-Cut.)$i=1,\ldots,n$$x_i$$1/2$$1/2$

Karena metode ini juga bekerja untuk Max-E3-SAT dan mencapai -approximation, ini adalah contoh dari algoritma serakah yang merupakan pendekatan yang optimal kecuali $7/8$ (cf. Hastad dan Moshkovitz-Raz hasil inapproximability untuk Max -E3-SAT).$P=NP$

Vertex Cover: Algoritma pendekatan faktor konstan terbaik melibatkan (dengan rakus) menemukan pencocokan maksimal dan memilih semua simpul yang terlibat sebagai solusi perkiraan. Ini menghasilkan solusi 2-perkiraan, dan tidak ada perkiraan faktor-konstan yang lebih baik adalah mungkin kecuali Dugaan Permainan Unik salah.

Subhash Khot dan Oded Regev, penutup Vertex mungkin sulit diperkirakan dalam 2 − ε , JCSS 74 (3), 2008.

Di luar topik: Saya pikir ini adalah algoritma perkiraan yang sangat lucu, terutama karena itu sangat sepele dengan manfaat dari belakang.

Diberikan grafik terarah, temukan subgraf asiklik dengan jumlah ujung maksimum.

Algoritma 2-aproksimasi trivial: Pilih urutan simpul yang sewenang-wenang dan ambil tepi maju atau mundur.

Mengalahkan 2-aproksimasi dikenal sebagai Unique-game hard (meskipun mungkin tidak NP-hard).

• Mengalahkan Urutan Acak Sulit: Ketidakpastian Subgraph Asiklik Maksimum Venkatesan Guruswami, Rajsekar Manokaran dan Prasad Raghavendra.

Maksimalisasi submodular sehubungan dengan batasan kardinalitas memiliki perkiraan serakah 1-1 / e. Algoritma adalah karena Nemhauser, Wolsey, Fisher. Kekerasan NP mengikuti dari np-hardness set cover karena max-coverage adalah kasus khusus dari maksimisasi submodular.

Greedy memberikan (1-1 / e) perkiraan untuk Max-k-cover, dan ini tidak dapat diperbaiki kecuali P = NP.

Menemukan gelar minimum MST. Sangat sulit karena menemukan jalur hamilton adalah kasus khusus. Algoritme pencarian lokal memberikan dalam konstanta aditif 1.

Referensi

Mendekati pohon Steiner derajat minimum ke dalam salah satu yang optimal

Itu $k$Masalah -center adalah masalah pengelompokan, di mana kita diberi grafik lengkap tidak terarah $G = (V,E)$ dengan jarak $d_{ij} \geq 0$ antara masing-masing pasangan simpul $i,j \in V$. Jarak mematuhi ketimpangan segitiga dan kesamaan model. Kami juga diberi bilangan bulat$k$.

Dalam masalah, kita harus menemukannya $k$kelompok yang mengelompokkan simpul yang paling mirip menjadi kelompok bersama. Kami memilih satu set$S \subseteq V, |S| = k$ dari $k$pusat cluster. Setiap dhuwur akan menugaskan dirinya ke pusat gugus terdekat yang mengelompokkan simpul ke dalamnya$k$cluster yang berbeda. Tujuannya adalah untuk meminimalkan jarak maksimum suatu titik ke pusat kelompoknya. Jadi secara geometris, kami ingin menemukan pusat$k$ bola yang berbeda dari jari-jari yang sama $r$ yang mencakup semua poin sehingga $r$ sekecil mungkin.

Algoritma optimal adalah serakah, dan juga sangat sederhana dan intuitif. Kami pertama-tama memilih titik$i \in V$ sewenang-wenang dan menaruhnya di set kami $S$pusat cluster. Kami kemudian memilih pusat klaster berikutnya sedemikian sehingga sejauh mungkin dari semua pusat klaster lainnya. Jadi sementara$|S| < k$, kami berulang kali menemukan simpul $j \in V$ untuk mana jaraknya $d(j,S)$ dimaksimalkan dan menambahkannya ke $S$. Sekali$|S| = k$ kita sudah selesai.

Algoritma yang dijelaskan adalah a $2$Algoritma-estimasi untuk $k$Masalah -center. Padahal, jika ada a$\rho$Algoritma-approximation untuk masalah dengan $\rho < 2$ kemudian $P = NP$. Ini dapat ditunjukkan dengan mudah dengan pengurangan dari masalah himpunan mendominasi NP-lengkap dengan menunjukkan kita dapat menemukan kumpulan ukuran yang mendominasi paling banyak$k$ iff sebuah instance dari $k$masalah -center di mana semua jarak adalah 1 atau 2 memiliki nilai optimal 1. Algoritma dan analisis diberikan oleh Gonzales, Clustering untuk meminimalkan jarak interluster maksimum, 1985 . Varian lain dari a$2$-approximation diberikan oleh Hochbaum dan Shmoys, heuristik terbaik untuk masalah k-center, 1985 .

Prosedur penjadwalan daftar Graham adalah optimal untuk penjadwalan dibatasi prioritas pada mesin identik $P|prec|C_{max}$ kecuali varian baru dari dugaan game unik oleh Bansal dan Khot salah.

Kekerasan Bersyarat dari Prasyarat Terkendala Penjadwalan pada Mesin Identik oleh Ola Svensson

Mungkin ini juga menarik bagi Anda (diadaptasi dari Metode untuk menerjemahkan kendala global ke kendala lokal )

Karena metode rakus (metode lokal yang lebih tepat ) hanya menggunakan informasi lokal untuk mencapai optimisasi global, jika ditemukan cara yang dapat mengubah kondisi global menjadi conditons yang dapat digunakan hanya dengan menggunakan informasi lokal, ini memberikan solusi optimal (global) untuk masalah. hanya menggunakan teknik lokal / serakah.

Referensi:

1. Berpikir Secara Global, Sesuai Secara Lokal: Pembelajaran Tanpa pengawasan dari Manifold Dimensi Rendah (Journal of Machine Learning Research 4 (2003))
2. Optimalisasi global menggunakan informasi lokal dengan aplikasi untuk kontrol aliran, Bartal, Y.
3. Mengapa Natural Gradient ?, Amari S., Douglas SC
4. Optimalisasi lokal untuk tujuan global: resolusi kebuntuan terdistribusi yang kompetitif dan alokasi sumber daya, Awerbuch, Baruch, Azar, Y.
5. Belajar dengan Konsistensi Lokal dan Global
6. Masalah Kepuasan Kendala yang Dipecahkan dengan Metode Konsistensi Lokal

Ada beberapa referensi yang menangani masalah menerjemahkan fungsi evaluasi global (atau kendala) ke yang lokal (menggunakan informasi lokal) dan konsistensi mereka (yaitu konvergensi ke optimum global yang sama):

1. Fungsi Evaluasi Lokal dan Fungsi Evaluasi Global untuk Evolusi Komputasi, HAN Jing, 2003
2. Munculnya dari Fungsi Evaluasi Lokal, Han Jing dan Cai Qingsheng, 2002

Abstrak (dari 1. di atas)

Makalah ini menyajikan pandangan baru pada evolusi komputasi dari aspek lokalitas dan globalitas fungsi evaluasi untuk memecahkan masalah kombinatorial klasik: Masalah kcoloring (masalah keputusan) dan Masalah Pewarnaan Minimum (masalah optimisasi). Kami pertama kali meninjau algoritma saat ini dan memodelkan masalah pewarnaan sebagai sistem multi-agen. Kami kemudian menunjukkan bahwa perbedaan penting antara algoritma tradisional (Pencarian Lokal, seperti Simulated Annealing) dan algoritma terdistribusi (seperti model Alife & AER) terletak pada fungsi evaluasi: Simulated Annealing menggunakan informasi global untuk mengevaluasi keadaan sistem secara keseluruhan, yang disebut metode Fungsi Evaluasi Global (GEF); model Alife & AER menggunakan informasi lokal untuk mengevaluasi keadaan agen tunggal, yang disebut metode Fungsi Evaluasi Lokal (LEF). Kami membandingkan kinerja metode LEF dan GEF untuk menyelesaikan Masalah pewarnaan-k dan Masalah Warna Minimum. Hasil eksperimen komputer menunjukkan bahwa LEF sebanding dengan metode GEF (Simulated Annealing dan Greedy), dalam banyak contoh masalah LEF mengalahkan metode GEF. Pada saat yang sama, kami menganalisis hubungan antara GEF dan LEF: konsistensi dan inkonsistensi. Teorema Konsistensi menunjukkan bahwa Nash Equilibria dari LEF identik dengan optima lokal GEF ketika LEF konsisten dengan GEF. Teorema ini sebagian menjelaskan mengapa LEF dapat memimpin sistem ke tujuan global. Beberapa aturan untuk membangun LEF yang konsisten diusulkan. Selain konsistensi,

Secara khusus makalah ini membahas metode untuk menentukan apakah fungsi lokal (LEF) konsisten dengan fungsi global (GEF) dan metode untuk membangun LEF yang konsisten dari GEF yang diberikan ( teorema Konsistensi ).

Kutipan dari bagian Kesimpulan (dari 1. di atas)

Makalah ini hanyalah awal dari studi LEF & GEF. Selain laporan penelitian di atas, masih banyak pekerjaan di masa depan: lebih banyak eksperimen tentang metode LEF; studi analitis tentang LEF; kecukupan informasi lokal untuk LEF; dan keberadaan GEF yang konsisten untuk setiap LEF; Apakah konsep konsistensi cukup? Karena Algoritma Genetika juga memiliki fungsi evaluasi (fungsi kebugaran), dapatkah kita menerapkan LEF & GEF ke Algoritma Genetika? ... Adalah niat kami untuk mempelajari dan berupaya menjawab semua pertanyaan ini