Tim peneliti ETH Zurich kembangkan algoritme aliran tercepat

 (ethz.ch)
1 poin oleh GN⁺ 2024-06-30 | 1 komentar | Bagikan ke WhatsApp
  • Tim riset Rasmus Kyng di ETH Zurich mengembangkan algoritme yang menghitung masalah menemukan aliran maksimum dalam jaringan sekaligus meminimalkan biaya transportasi dengan kecepatan yang nyaris mencapai batas matematis
  • Algoritme baru ini memakai pendekatan hampir waktu linear, yang menghasilkan jawaban dalam skala waktu yang hampir sama dengan waktu membaca data jaringan, dan dapat diterapkan pada perhitungan jaringan seperti rel kereta, jalan raya, jalur air, dan internet
  • Sebelumnya, jika jumlah koneksi dinyatakan sebagai m, hingga sebelum tahun 2000 kecepatannya berada di kisaran m^1.5, dan pada 2004 sekitar m^1.33, tetapi pendekatan Kyng menurunkan waktu komputasi tambahan setelah pembacaan data ke tingkat yang nyaris bisa diabaikan
  • Tim peneliti juga menghitung lintasan terpendek dan aliran maksimum biaya minimum dalam hampir waktu linear, melampaui jaringan statis dan berarah ke graf inkremental tempat koneksi ditambahkan dan graf dekremental tempat koneksi dihapus
  • Ini menjadi dasar untuk menghitung ulang rute optimal dengan cepat ketika jaringan dunia nyata berubah, seperti penutupan dan pembukaan kembali sebagian Gotthard Base Tunnel atau longsor di jalan tol A13

Menghitung masalah aliran jaringan nyaris pada batas kecepatan

  • Algoritme aliran jaringan dari tim Rasmus Kyng menangani masalah mencari aliran maksimum yang mungkin di jaringan sambil meminimalkan biaya transportasi
  • Contoh yang representatif adalah mencari rute untuk memindahkan sebanyak mungkin barang dari Copenhagen ke Milan secepat dan semurah mungkin
  • Aliran berbiaya rendah yang optimal dapat dihitung pada jaringan dengan koneksi dan kapasitas seperti rel kereta, jalan, jalur air, dan internet
  • Kecepatan komputasinya ditekan hingga hampir setara dengan waktu yang dibutuhkan komputer untuk membaca data jaringan

Mengapa ini disebut algoritme “tercepat”

  • Sebelumnya, waktu untuk menghitung aliran optimal jauh lebih lama daripada waktu yang dibutuhkan untuk memproses data jaringan
  • Semakin besar dan kompleks jaringannya, waktu komputasi yang dibutuhkan meningkat lebih cepat daripada ukuran masalah itu sendiri
  • Pendekatan Kyng membuat waktu komputasi dan ukuran jaringan meningkat dengan rasio yang sama
    • Jika jumlah koneksi jaringan adalah m, maka hanya untuk membaca data satu kali saja dibutuhkan waktu m
    • Hingga sebelum tahun 2000, tidak ada algoritme yang dapat menghitung lebih cepat dari m^1.5
    • Pada 2004, jumlah komputasi yang dibutuhkan untuk menyelesaikan masalah turun hingga m^1.33
    • Algoritme Kyng menurunkan waktu komputasi tambahan untuk mencapai solusi setelah membaca data ke tingkat yang nyaris bisa diabaikan

Penilaian dan perluasan algoritme hampir waktu linear

  • Dua tahun lalu, tim Kyng menerbitkan makalah yang memuat pembuktian matematis konsep ini
  • Algoritme yang nyaris optimal secepat ini disebut algoritme hampir waktu linear
  • Daniel A. Spielman mengibaratkan algoritme ini seperti Porsche yang menyalip kereta kuda
  • Makalah tersebut memenangkan Best Paper Award di IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
  • Communications of the ACM juga menyoroti riset ini, dan редакси Quanta memilih algoritme Kyng sebagai salah satu dari 10 penemuan teratas ilmu komputer pada 2022

Dari jaringan statis ke jaringan yang berubah

  • Algoritme awal berfokus pada jaringan tetap dan statis dengan arah koneksi yang sudah ditentukan
    • Koneksi berarah adalah struktur seperti jalan satu arah pada jaringan jalan kota
  • Setelah itu, tim peneliti mengembangkan algoritme untuk menghitung aliran optimal pada jaringan yang berubah secara bertahap seiring waktu
  • Simon Meierhans mempresentasikan algoritme hampir waktu linear baru di Annual ACM Symposium on Theory of Computing, STOC, di Vancouver
    • Algoritme ini menyelesaikan masalah aliran maksimum biaya minimum pada jaringan yang mendapat tambahan koneksi baru
  • Dalam makalah kedua yang diterima di IEEE Symposium on Foundations of Computer Science, FOCS, pada Oktober, mereka mengembangkan algoritme yang juga menangani penghapusan koneksi
  • Kedua algoritme tersebut mengidentifikasi lintasan terpendek pada jaringan tempat koneksi ditambahkan atau dihapus

Contoh perubahan jaringan di dunia nyata

  • Gotthard Base Tunnel di Switzerland sempat ditutup total sejak musim panas 2023 lalu dibuka kembali sebagian
  • Sebagian jalan tol A13, rute alternatif utama untuk Gotthard Road Tunnel, baru-baru ini rusak akibat longsor
  • Jika perubahan seperti ini terjadi, komputer, layanan peta online, dan perencana rute harus menghitung ulang koneksi berbiaya terendah dan terpendek antara Milan dan Copenhagen
  • Algoritme baru Kyng menghitung rute optimal dalam hampir waktu linear bahkan pada jaringan dengan penambahan atau penghapusan koneksi
  • Bahkan ketika koneksi ditambahkan karena adanya jalan memutar atau rute baru, waktu komputasi tambahan tetap berada pada tingkat yang nyaris bisa diabaikan

Dua strategi lama dan cara penggabungan baru

  • Perhitungan aliran jaringan perlu menganalisis jaringan berkali-kali untuk menemukan aliran optimal dan rute biaya minimum
  • Pada tiap iterasi, perubahan seperti koneksi mana yang terbuka, tertutup, atau mencapai batas kapasitas hingga macet akan ditinjau
  • Sebelum Kyng, ilmuwan komputer umumnya menggunakan salah satu dari dua strategi
    • Model jaringan rel: pada tiap iterasi, seluruh satu bagian dari jaringan yang aliran lalu lintasnya berubah dihitung
    • Model jaringan listrik: pada tiap iterasi, seluruh jaringan dihitung, tetapi perhitungan dipercepat dengan memakai nilai rata-rata statistik untuk aliran yang berubah di tiap bagian
  • Tim Kyng menggabungkan keunggulan kedua strategi itu menjadi pendekatan gabungan yang baru
  • Maximilian Probst Gutenberg menilai bahwa menggabungkan banyak langkah komputasi kecil yang efisien dan murah jauh lebih cepat daripada beberapa langkah besar

Konteks historis algoritme aliran

  • Masalah aliran jaringan adalah salah satu masalah awal yang diselesaikan secara sistematis dengan algoritme pada 1950-an
  • Algoritme aliran memainkan peran penting dalam memantapkan ilmu komputer teoretis sebagai bidang riset yang mandiri
  • Algoritme terkenal dari Lester R. Ford Jr. dan Delbert R. Fulkerson juga muncul pada periode ini
  • Algoritme Ford-Fulkerson secara efisien menyelesaikan masalah aliran maksimum, yaitu mengangkut sebanyak mungkin barang melalui jaringan tanpa melampaui kapasitas tiap rute
  • Riset selanjutnya menunjukkan bahwa masalah aliran maksimum, masalah biaya minimum, dan berbagai masalah aliran jaringan lainnya adalah kasus khusus dari masalah aliran biaya minimum yang lebih umum

Keterbatasan algoritme sebelumnya dan titik balik 2004

  • Banyak algoritme sebelum riset Kyng dapat menyelesaikan satu masalah tertentu secara efisien, tetapi belum cukup cepat dan sulit diperluas ke masalah aliran biaya minimum yang lebih luas
  • John Edward Hopcroft, Richard Manning Karp, dan Robert Endre Tarjan, yang menciptakan algoritme aliran perintis pada 1970-an, masing-masing menerima Turing Award
    • Karp menerimanya pada 1985
    • Hopcroft dan Tarjan menerimanya pada 1986
  • Pada 2004, Daniel Spielman, Shang-Hua Teng, dan kemudian Samuel Daitch menulis algoritme yang memberikan solusi cepat dan efisien juga untuk masalah aliran biaya minimum
  • Kelompok ini menggeser sudut pandang dari rel kereta ke aliran listrik dalam jaringan listrik
  • Dalam jaringan listrik, arus dapat sebagian dialihkan melalui koneksi yang sudah dilalui arus lain
  • Kyng tidak langsung mengikuti pendekatan algoritmik kuat Spielman untuk seluruh jaringan, tetapi menerapkan gagasan perhitungan jalur parsial pada pendekatan sebelumnya dari Hopcroft dan Karp
  • Fakta bahwa jalur parsial dihitung pada setiap iterasi berperan besar dalam mempercepat perhitungan seluruh aliran

Alat matematika baru dan struktur data

  • Kemajuan tim riset ETH Zurich tidak hanya bertumpu pada algoritme baru, tetapi juga pada perancangan alat matematika yang mempercepat komputasi
  • Tim peneliti mengembangkan struktur data baru untuk mengatur data jaringan
  • Struktur data ini memungkinkan perubahan pada koneksi jaringan diidentifikasi dengan sangat cepat
  • Identifikasi perubahan yang cepat menjadi faktor yang meningkatkan kecepatan solusi algoritmik
  • Algoritme hampir waktu linear dan struktur data baru ini meletakkan dasar untuk menyelesaikan masalah sangat besar yang sebelumnya tidak bisa dihitung secara efisien

Makalah dan materi terkait

Bacaan terkait

1 komentar

 
GN⁺ 2024-06-30
Opini Hacker News

  • Algoritma ini secara asimtotik hampir linear pada limit n -> inf
    Di akhir video disebutkan bahwa implementasi apa pun dari algoritma ini akan sulit mengalahkan algoritma yang sudah ada di dunia nyata
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • Jadi ini satu lagi algoritma galaktik?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • Setelah bagian awal membangun ekspektasi besar, ini terasa cukup antiklimaks
    • Begitu melihat judulnya, saya langsung sangat skeptis
      Ungkapan kecepatan tercepat yang mungkin adalah klaim yang benar-benar berani
    • Dalam kasus seperti ini, petunjuk lain adalah bahwa biasanya dibutuhkan solusi optimal absolut
      Sering kali jauh lebih praktis memakai 1% waktu untuk mendapatkan 99% kualitas

  • Menariknya, orang yang sama juga meneliti cara membuat algoritma khusus teori benar-benar bekerja dengan baik dalam praktik [1]
    Namun proses itu tampaknya butuh sekitar 20 tahun lagi. [1] dibangun di atas terobosan teoretis tahun 2004 [2], dan sejauh yang saya pahami, algoritma-algoritma seperti ini baru mulai bekerja di praktik pada 2024. Jadi mungkin kita bisa menantikan algoritma minimum cost flow yang praktis pada 2044
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    Beralih dari O(mn) ke O(m) berarti mengeluarkan N, yaitu jumlah simpul, dari komputasi; bukankah itu terlalu bagus untuk dipercaya?

    • Faktor konstanta-nya begitu besar sehingga pada input praktis kemungkinan akan lebih lambat daripada algoritma lama yang secara asimtotik lebih buruk
      Tetap saja, secara teoretis ini hasil yang keren

  • Bahkan dari angka mentah saja terlihat seberapa jauh kita sudah melangkah. Sebelum tahun 2000-an, tidak ada algoritma yang bisa menghitung lebih cepat dari m1.5. Di sini m berarti jumlah koneksi jaringan yang harus dihitung komputer, dan membaca data jaringan satu kali saja memerlukan waktu m. Pada 2004, kecepatan komputasi yang diperlukan untuk menyelesaikan masalah ini turun menjadi m1.33. Dengan algoritma Kyng, setelah membaca data jaringan, waktu komputasi “tambahan” yang diperlukan untuk mencapai solusi kini dapat diabaikan.
    Artikel aslinya tidak menjelaskan terobosan Kyng dari sudut pandang metrik m yang justru diperlakukan sepenting itu; saya penasaran kenapa

  • Kadang rasanya kita benar-benar tersesat ketika menjadikan kompleksitas sebagai metrik
    Makin banyak algoritma yang mengoptimalkan metrik kompleksitas sampai tingkat gila-gilaan, tetapi sebenarnya tidak berguna

    • Fenomena seperti itu sudah ada selama puluhan tahun
      Setelah semua hasil yang mudah habis, riset algoritma menjadi satu lagi bidang yang sangat terspesialisasi, dan kecuali Anda peneliti di bidang yang sangat dekat, sebagian besar makalah tidak terlalu sepadan untuk dibaca

  • Tulisan terkait: https://news.ycombinator.com/item?id=31149038 (40 komentar)
    https://news.ycombinator.com/item?id=31675015 (72 komentar)

  • Di mana makalah atau kode-nya?

  • Ada bagian yang membingungkan di sini: o(n) tampak seperti pernyataan yang lebih kuat daripada O(n)
    Karena setiap algoritma o(n) adalah O(n), tetapi sebaliknya tidak benar. Selain itu, jika o(n) berlaku bahkan untuk n sekecil apa pun, sedangkan O(n) hanya berlaku saat n -> inf, bukankah algoritma ini seharusnya juga berlaku untuk n kecil? Kalau begitu bukankah ini harus menjadi kebalikan dari algoritma galaktik yang disebut di atas? Apakah ada yang saya lewatkan?

    • Notasi o kecil juga tetap merupakan pernyataan asimtotik, jadi tidak harus berlaku untuk n kecil
      Definisi f(n) = o(g(n)) kira-kira adalah lim (n -> infinity) f(n)/g(n) = 0. Dengan kata lain, untuk n yang cukup besar, g tumbuh lebih cepat daripada f
      Misalnya, fungsi seperti f(n) = 10n if n < 1000 else 1e1000 adalah o(n). Ketika n membesar, 1e1000/n menuju 0. Ini adalah representasi pseudo-Python dari fungsi bertahap yang naik secara eksponensial sampai 101000 hingga n = 1000, lalu tetap konstan setelah itu
    • Jika kompleksitas algoritma adalah 3↑↑64*n^0.999, maka algoritma itu o(n), tetapi tetap aman disebut algoritma galaktik

  • Kalau ingatan saya benar, 3↑↑64 adalah bilangan Graham

  • Sialan faktor konstanta itu, bikin ingin mengacungkan tinju ke langit

  • Di abstraknya hanya tertulis waktunya m^(1+o(1))
    Ada yang tahu apakah batas atas yang lebih konkret tercantum di suatu tempat?

    • Di sini o adalah o kecil, jadi ia menangkap suku yang “nilainya dibagi 1” menuju 0 ketika m menuju tak hingga
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Artinya kita bisa memilih konstanta agar sedekat yang diinginkan ke O(m)
      Dengan kata lain, ini adalah skema algoritma yang untuk sembarang ɛ>1 memberi algoritma yang berjalan dalam waktu O(m^ɛ)
    • Itulah batas atas konkretnya
      o kecil adalah fungsi yang mendekati 0 ketika n menuju tak hingga, dan disebut dapat diabaikan secara asimtotik