Seberapa mendasar matroid dan greedoid dalam desain algoritma?

Awalnya, matroids diperkenalkan untuk menggeneralisasi pengertian kemerdekaan linear dari koleksi himpunan bagian atas beberapa tanah ditetapkan . Masalah-masalah tertentu yang mengandung struktur ini memungkinkan algoritma serakah untuk menemukan solusi optimal. Konsep greedoid kemudian diperkenalkan untuk menggeneralisasi struktur ini untuk menangkap lebih banyak masalah yang memungkinkan ditemukannya solusi optimal dengan metode serakah. $E$ $I$

Seberapa sering struktur ini muncul dalam desain algoritma?

Lebih jauh, lebih sering daripada tidak algoritma serakah tidak akan dapat sepenuhnya menangkap apa yang diperlukan untuk menemukan solusi optimal, tetapi mungkin masih menemukan solusi perkiraan yang sangat baik (Bin Packing, misalnya). Mengingat bahwa, apakah ada cara untuk mengukur seberapa "dekat" masalah dengan greedoid atau matroid?

algorithms optimization combinatorics greedy-algorithms matroids Nicholas Mancuso
sumber

Jawaban:

Sulit untuk menjawab pertanyaan "seberapa sering". Tetapi seperti halnya dengan semua "struktur dasar", manfaatnya berasal dari pengakuan bahwa masalah mendasar yang sedang dicoba diselesaikannya memiliki struktur matroid (atau greedoid). Bukan hanya masalah matroid. Masalah persimpangan matroid memiliki model khusus (pencocokan bipartit).

Nick Harvey melakukan tesis Ph.D-nya baru-baru ini pada algoritma untuk masalah matroid dan juga melihat optimasi fungsi submodular (yang menggeneralisasikan masalah matroid). Membaca pengantar dan latar belakang tesis ini mungkin bisa membantu.

Suresh
sumber

Saya hanya ingin menambahkan catatan tentang "kedekatan". Jika algoritma serakah memberikan perkiraan-k, masalahnya mungkin terstruktur sebagai k-matroid.

Nicholas Mancuso

+1. Jawaban bagus. Saya bertanya-tanya mengapa tesis mengatakan fungsi submodular adalah generalisasi atau abstrak dari matroid? Satu-satunya koneksi yang saya dapat temukan di antara keduanya adalah pangkat submatroid pada subset adalah fungsi submodular.

Tim

Ada koneksi geometris yang sangat elegan. Untuk memahami ini dengan lebih baik, Anda harus memeriksa en.wikipedia.org/wiki/Polymatroid . Secara kasar, jika polytope yang terkait dengan fungsi submodular memiliki sifat spesifik, maka Anda mendapatkan matroid. Untuk informasi lebih lanjut tentang ini, lihat buku Satoru Fujishige: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html

Suresh

Seperti ditunjukkan dalam CLRS (halaman 437 edisi 3), teori matroid tidak mencakup masalah pemilihan aktivitas dan masalah pengkodean Huffman. Apakah teori greedoid melindungi mereka?

hengxin