Nuovo algoritmo di flusso di ETH Zurich rivoluziona la velocità del calcolo nei network

RomeUn team di ricercatori dell'ETH di Zurigo, guidato da Rasmus Kyng, ha sviluppato il più rapido algoritmo per risolvere i problemi di flusso di rete. Questo nuovo metodo promette di rivoluzionare il calcolo dei flussi ottimali nelle reti.

L'algoritmo di Kyng risolve il problema del flusso massimo. Determina il modo più efficiente per spostare beni attraverso una rete minimizzando i costi. Questo metodo può essere applicato a vari tipi di reti come sistemi di trasporto e internet.

Ecco alcuni punti chiave sul nuovo algoritmo:

• Calcola il flusso di rete ottimale quasi istantaneamente dopo aver letto i dati
• Adatto per reti statiche e in evoluzione
• Gestisce sia l'aggiunta che la rimozione di connessioni di rete
• Riconosciuto come una delle dieci più grandi scoperte nel campo dell'informatica del 2022
• Vincitore del Miglior Articolo del 2022 al Simposio Annuale IEEE sulle Fondamenta dell'Informatica (FOCS)

In passato, trovare le migliori rotte nelle reti richiedeva molto tempo. Con l'aumento delle dimensioni e della complessità delle reti, il tempo necessario per calcolarle cresceva ulteriormente. Tuttavia, il metodo Kyng garantisce che il tempo richiesto per il calcolo e la dimensione della rete aumentino alla stessa velocità.

Fino al 2004, i migliori algoritmi potevano calcolare i flussi in una rete con una complessità temporale proporzionale al numero di connessioni elevato alla potenza di 1,5. Nel 2004, questa complessità è stata ridotta a una potenza di 1,33. Ora, l'algoritmo di Kyng diminuisce ulteriormente il tempo di calcolo in maniera significativa.

Il lavoro di Kyng è in fase di miglioramento. I nuovi algoritmi aggiornati ora funzionano per reti che cambiano nel tempo. Calcolano i migliori flussi rapidamente, anche in reti con molte variazioni. Questo è fondamentale per reti reali come sistemi di traffico che sono sempre in evoluzione.

Simon Meierhans dell'ETH ha presentato un algoritmo veloce al Simposio ACM sulla teoria del calcolo a Vancouver. Questo algoritmo risolve il problema del flusso massimo a costo minimo per reti che cambiano gradualmente.

Il team ha pubblicato un altro articolo, accettato da FOCS, in cui hanno sviluppato un algoritmo per gestire la rimozione di connessioni. Questo risulta utile in situazioni reali come la chiusura e riapertura di percorsi stradali.

Il team di Kyng ha sviluppato un nuovo metodo migliorando le tecniche precedenti, utilizzando molti piccoli passi anziché lavorare su grandi sezioni. Questo approccio rende i calcoli molto più veloci.

Negli anni '50, i ricercatori iniziarono a risolvere sistematicamente i problemi di flusso nelle reti. In questo periodo, Lester R. Ford Jr. e Delbert R. Fulkerson svilupparono algoritmi fondamentali. Affrontarono il problema del flusso massimo, che riguarda il movimento efficiente di beni attraverso una rete.

La maggior parte dei precedenti algoritmi era efficace ma lenta. L'algoritmo di Kyng risulta essere sia efficace che veloce. Prima di Kyng, i ricercatori si concentravano o sui modelli ferroviari o su quelli della rete elettrica. Il metodo di Kyng combina i migliori aspetti di entrambi i modelli.

Il team ha sviluppato nuovi strumenti matematici per accelerare i loro algoritmi. Hanno creato un sistema innovativo per organizzare i dati di rete, permettendo di identificare rapidamente le variazioni nelle connessioni. Questo rende l'algoritmo notevolmente più veloce.

I ricercatori dell'ETH di Zurigo hanno ideato nuovi algoritmi estremamente veloci. Questi algoritmi risolvono grandi problemi rapidamente, rivoluzionando il modo in cui i computer gestiscono compiti complessi.

Questa ricerca è fondamentale nell'informatica. Migliora la gestione di grandi e dinamiche reti di dati. Trova applicazione in molteplici campi, tra cui la biologia e le reti sociali.