Módosított Bellman–Ford algoritmus arbitrázs kereséshez
| Témavezető: | Bérczi-Kovács Erika Renáta |
| ELTE, Operációkutatási Tanszék | |
| email: | erika.berczi-kovacs@ttk.elte.hu |
Témavezetők
- Tapolcai János (BME VIK TMIT)
Projekt leírás
A Bellman–Ford algoritmus képes körök detektálására súlyozott gráfokban. Adaptációja során az a feladat, hogy találjunk arbitrázsköröket egy exchange graph-ban, ahol a csúcsok tokeneket, az élek pedig AMM-ek által meghatározott cserelehetőségeket jelentenek.
Leírás: Minden élhez tartozik egy w_e(x_{in}) függvény (kimeneti token mennyiség) és egy g_e(x_{in}) függvény (gázköltség). Az AMM-ek állapota minden swap után változik, ezért ugyanazt a poolt egy körben legfeljebb egyszer lehet használni. Egy arbitrázskör akkor profitábilis, ha a kör végére visszakapott tokenmennyiség meghaladja a kezdeti inputot, figyelembe véve a gázköltséget.
Feladat: A módosított Bellman–Ford algoritmus megvalósítása, amely képes profitábilis arbitrázskörök detektálására, megfelelő adattárolás az utak és távolságok nyilvántartására.