Algoritma Daring

Algoritma daring harus membuat keputusan yang tidak dapat diubah saat masukan tiba, tanpa pengetahuan tentang permintaan di masa mendatang; kualitasnya diukur dengan analisis kompetitif terhadap algoritma optimal yang melihat seluruh masukan terlebih dahulu.

Definition

Algoritma daring menerima masukannya sebagai urutan permintaan dan harus menanggapi setiap permintaan dengan segera dan tidak dapat diubah tanpa melihat permintaan di masa mendatang; rasio kompetitifnya adalah rasio kasus terburuk dari biayanya terhadap biaya algoritma luring optimal yang mengetahui seluruh urutan permintaan.

Scope

Topik ini mencakup algoritma yang memproses masukan secara berurutan dan membuat keputusan sebelum masukan selanjutnya diketahui, serta kerangka rasio kompetitif yang digunakan untuk mengevaluasinya terhadap musuh luring (offline adversary) yang optimal. Ini mencakup masalah klasik — paging dan caching, pembaruan daftar, masalah penyewaan ski, masalah k-server, serta penjadwalan daring dan pengepakan bin — dan peran randomisasi dalam meningkatkan rasio kompetitif terhadap musuh yang lebih lemah.

Core questions

• Bagaimana algoritma daring dievaluasi ketika masa depan tidak diketahui?
• Apa yang diukur oleh rasio kompetitif, dan apa itu musuh luring?
• Bagaimana masalah klasik seperti paging dan penyewaan ski menggambarkan pertukaran daring?
• Bagaimana randomisasi dapat meningkatkan daya saing terhadap musuh yang tidak menyadari?
• Batasan bawah apa yang membatasi seberapa kompetitif algoritma daring mana pun?

Key concepts

• daring versus luring
• rasio kompetitif
• musuh luring
• paging dan caching
• pembaruan daftar
• masalah penyewaan ski
• masalah k-server
• daya saing acak

Key theories

Analisis kompetitif

Analisis kompetitif menilai algoritma daring berdasarkan rasio kasus terburuk antara biayanya dan biaya algoritma luring optimal, memberikan jaminan yang berlaku untuk urutan masukan apa pun daripada mengandalkan asumsi tentang masukan.

Randomisasi terhadap musuh yang tidak menyadari

Algoritma daring acak dapat mencapai rasio kompetitif yang secara signifikan lebih baik daripada algoritma deterministik mana pun terhadap musuh yang tidak menyadari, karena musuh harus memperbaiki masukan tanpa mengetahui pilihan acak algoritma.

Clinical relevance

Algoritma daring memodelkan keputusan yang dibuat sistem secara waktu nyata tanpa pengetahuan di masa mendatang: penggantian cache dan halaman dalam sistem operasi dan CPU, pengorganisasian mandiri struktur data, alokasi sumber daya dinamis dan penyeimbangan beban, serta keputusan sewa-atau-beli dalam komputasi awan. Analisis kompetitif memberikan jaminan kasus terburuk untuk sistem reaktif semacam itu.

History

Analisis kompetitif diperkenalkan oleh Sleator dan Tarjan pada tahun 1985 melalui studi mereka tentang aturan pembaruan daftar dan paging, membingkai ulang evaluasi algoritma daring di sekitar perbandingan dengan solusi luring yang optimal. Kerangka kerja ini berkembang melalui masalah k-server dan algoritma daring acak pada tahun 1990-an, yang disurvei dalam monograf Borodin dan El-Yaniv tahun 1998.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

Apa itu rasio kompetitif?

Ini adalah rasio kasus terburuk dari biaya algoritma daring terhadap biaya algoritma optimal yang melihat seluruh masukan terlebih dahulu. Algoritma 2-kompetitif tidak pernah berbiaya lebih dari dua kali biaya luring terbaik yang mungkin pada urutan masukan apa pun.

Mengapa randomisasi membantu algoritma daring?

Terhadap musuh yang tidak menyadari yang memperbaiki masukan tanpa melihat pilihan acak algoritma, randomisasi mencegah musuh menyesuaikan kasus terburuk dengan perilaku algoritma, memungkinkan rasio kompetitif yang secara signifikan lebih baik daripada yang dapat dicapai oleh algoritma deterministik mana pun.