Apa itu algoritma aproksimasi bicriteria?

11

Apa itu algoritma aproksimasi bicriteria? Ini terus muncul dalam kasus pengelompokan aliran data. Apakah ini terkait dengan optimasi multi-tujuan?

Di sinilah saya menemukan itu: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Makalah ini tentang versi streaming dari algoritma k-means. Ada referensi dalam makalah tetapi tidak satupun dari mereka memberikan penjelasan tentang apa algoritma pendekatan bikriteria. Sepertinya saya tidak dapat menemukan apa pun di Google yang akan memberi saya definisi yang tepat juga.

Suhas Lohit
sumber
1
Saya tidak tahu Di mana Anda melihatnya disebut? Bisakah Anda memberikan tautan dan kutipan yang tepat ke satu atau lebih sumber yang menggunakan terminologi ini? Dari namanya, memang terdengar seperti optimasi multi-objektif (dengan dua fungsi objektif), tetapi mungkin sulit untuk mengatakannya tanpa konteks lebih lanjut. Juga, penelitian apa yang Anda lakukan? Apakah Anda mencari di Google?
DW
Saya sarankan Anda mengedit pertanyaan. Pertanyaan diharapkan untuk berdiri sendiri; orang harus dapat memahami semua yang perlu mereka ketahui dari membaca hanya pertanyaan itu sendiri, bukan komentar. Komentar ada hanya untuk membantu Anda meningkatkan pertanyaan. Anda dapat mengklik tombol "edit" di bawah pertanyaan Anda untuk memperbaikinya. PS Saya sarankan Anda juga menjawab pertanyaan saya yang lain. Penelitian apa yang Anda lakukan? (Di situs ini, kami berharap Anda melakukan riset sendiri sebelum bertanya di sini.)
DW

Jawaban:

11

Saya akan memperluas jawaban oleh Yuval Filmus dengan memberikan interpretasi berdasarkan masalah optimasi multi-objektif .

Optimalisasi dan pendekatan objektif tunggal

Dalam ilmu komputer kita sering mempelajari masalah optimisasi dengan satu tujuan (misalnya, meminimalkan f ( x ) tunduk pada beberapa kendala). Saat membuktikan, katakanlah, kelengkapan NP, adalah umum untuk mempertimbangkan masalah anggaran terkait . Misalnya, dalam masalah klik maksimum, tujuannya adalah untuk memaksimalkan kardinalitas klik, dan masalah anggaran adalah masalah memutuskan apakah ada klik ukuran setidaknya k , di mana k diberikan sebagai bagian dari input untuk masalah.

Ketika tidak mungkin untuk menghitung solusi optimal secara efisien, seperti dalam kasus masalah klik maksimum, kami mencari algoritma aproksimasi , suatu fungsi yang menghasilkan solusi dalam faktor multiplikasi dari solusi optimal. Anda juga dapat mempertimbangkan algoritma perkiraan untuk masalah anggaran, fungsi yang menghasilkan solusi yang memenuhi f ( x ) ≥ ck dalam kasus masalah maksimalisasi, di mana c adalah angka kurang dari satu. Dalam situasi ini, solusinya mungkin melanggar batasan keras f ( x ) ≥ k , tetapi "tingkat keparahan" pelanggaran dibatasi oleh c .

Optimalisasi multi-tujuan dan pendekatan dua kriteria

Dalam beberapa kasus, Anda mungkin ingin mengoptimalkan dua tujuan secara bersamaan. Sebagai contoh kasar, saya mungkin ingin memaksimalkan "pendapatan" saya sambil meminimalkan "biaya" saya. Dalam situasi seperti itu, tidak ada nilai optimal tunggal, karena ada tradeoff antara kedua tujuan; untuk informasi lebih lanjut, lihat artikel Wikipedia tentang efisiensi Pareto .

Salah satu cara untuk mengubah masalah pengoptimalan dua-tujuan menjadi masalah pengoptimalan satu-tujuan (yang dapat kami alasan tentang nilai optimal dari fungsi tujuan) adalah dengan mempertimbangkan dua masalah kendala , satu untuk setiap tujuan. Jika masalahnya adalah memaksimalkan secara simultan f ( x ) sambil meminimalkan g ( x ), masalah kendala pertama adalah meminimalkan g ( x ) tunduk pada kendala f ( x ) ≥ k , di mana k diberikan sebagai bagian dari input untuk masalah optimasi satu-tujuan ini. Masalah kendala kedua didefinisikan secara serupa.

Algoritma pendekatan bikriteria ( α , β ) - untuk masalah kendala pertama adalah fungsi yang mengambil parameter anggaran k sebagai input dan menghasilkan solusi x sedemikian rupa sehingga

  • f(x)αk ,
  • g(x)βg(x) ,

di mana adalah solusi yang mencapai nilai optimal untuk g . Algoritma pendekatan bicriteria untuk masalah kendala kedua menghasilkan solusi sedemikian rupax

  • f(x)αf(x) ,
  • g(x)β ,

Dengan kata lain, algoritma aproksimasi bikriteria secara bersamaan merupakan suatu aplikasi untuk masalah anggaran dalam tujuan pertama dan masalah optimasi dalam tujuan kedua. (Definisi ini diadaptasi dari halaman empat " Optimalisasi Submodular dengan Submodular Cover dan Submodular Knapsack Constraints ", oleh Iyer dan Bilmes, 2013.)

Ketidaksetaraan beralih arah ketika tujuan beralih dari maksimum ke minimum atau sebaliknya.

argentpepper
sumber
6

Seringkali, masalah optimasi melibatkan beberapa parameter. Sebagai contoh, perhatikan masalah partisi grafik. Diberikan grafik berbobot, bilangan bulat , dan parameter , kami ingin mempartisi set simpul menjadi bagian ukuran paling banyak sambil meminimalkan jumlah tepi potong (tepi yang menghubungkan simpul-simpul milik bagian-bagian berbeda). Perhatikan bahwa ada dua parameter di sini: dan jumlah tepi potong.kρkV1,,VkρE(V1,,Vk)ρ

Untuk , a algoritma pendekatan bikriteria akan menghasilkan partisi mana setiap bagian berukuran paling banyak , dan jumlah tepi potong paling banyak , di mana adalah jumlah optimal tepi potong dalam masalah awal , dengan bagian-bagian dibatasi pada ukuran paling banyak .f(n),g(n)1f(n),g(n)V1,,Vkf(n)ρg(n)OPTOPTρ

Dengan kata lain, algoritma aproksimasi bicriteria mencapai rasio aproksimasi tertentu sambil melanggar beberapa batasan dengan jumlah yang dibatasi. Untuk contoh algoritme pendekatan bikriteria untuk masalah yang baru saja dijelaskan, lihat makalah ini oleh Makarychev bersaudara.

Yuval Filmus
sumber