Fungsi submodular: permintaan referensi

11

Saya akan sangat tertarik pada referensi ke teori fungsi submodular (dari dasar ke lanjutan).

Secara khusus, saya sedang mempelajari perkiraan untuk masalah optimasi keras dan saya ingin mengembangkan dasar saya dalam fungsi submodular karena mereka relevan dengan masalah optimasi yang telah saya pelajari.

Terima kasih sebelumnya.

Nikhil
sumber

Jawaban:

8

Referensi seperti yang disarankan oleh Standa Zivny tentu saja sangat bagus. Izinkan saya menambah daftar buku baru karya Andras Frank berjudul "Connections in Combinatorial Optimization" yang diterbitkan oleh Oxford University Press, 2011. Semua referensi ini memperlakukan fungsi submodular dari sudut pandang optimasi kombinatorial klasik di mana submodularity terutama muncul dalam kendala. Ada beberapa aplikasi dan perkembangan terkini dengan fungsi tujuan submodular yang membutuhkan sudut pandang yang sedikit berbeda. Ada banyak makalah untuk diberikan daftar di sini. Namun saya akan merekomendasikan survei Shaddin Dughmi tentang ekstensi terus menerus dari fungsi submodular http://arxiv.org/abs/0912.0322v3 .

Chandra Chekuri
sumber
Terima kasih atas surveynya, ini terlihat sangat bagus! Saya baru-baru ini membeli buku Frank, tetapi belum mengelola untuk membacanya sehingga saya agak enggan untuk merekomendasikannya.
Standa Zivny
5
@Chandra, saatnya bagi Anda untuk menulis survei tentang hal-hal terbaru :)
Suresh Venkat
Terima kasih atas tautan survei. Saya mencari sesuatu yang mirip dengan ini.
Nikhil
9

Referensi yang saya gunakan (dan sejenisnya) adalah bab-bab terpilih dalam 3-volume Optimasi Kombinatorial Schrijver: Polihedra dan Efisiensi (Springer) dan Vygen's Combinatorial Optimization (Springer). Ada buku yang dikhususkan untuk fungsi submodular oleh Fujishige: Fungsi dan Optimasi Submodular, volume 58 dari Annals of Discrete Mathematics, North-Holland (edisi ke-2 dari 2005).

Standa Zivny
sumber
2

Salah satu favorit saya, tesis Jan vondrak dan banyak makalahnya.

Ashwinkumar BV
sumber
0

Dua publikasi lagi 1. Goldengorin, B., Ghosh, D .: Algoritme pencarian bertingkat untuk memaksimalkan fungsi submodular yang diterapkan pada masalah partisi biaya kuadratik. J. Glob. Optim. 32, 65–82 (2005)

  1. B. Goldengorin. Maksimalisasi fungsi submodular: Teori dan algoritma enumerasi. European Journal of Operational Research, 198 (1): 102-112, 2009
pengguna56394
sumber