Motivazione

F. Grandoni, J. Könemann, Alessandro Panconesi, and Mauro Sozio. Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. Proceedings of Twenty-Fourth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), July 17-20, 2005, Las Vegas, Nevada, USA.

Nel lavoro premiato viene introdotto un metodo che permette di trasformare in modo sistematico un algoritmo primal-dual sequenziale in un algoritmo distribuito approssimato. Tale metodo e' applicato al problema del ricoprimento tramite nodi con capacita'. Tale problema e' una variante del fondamentale problema del ricoprimento tramite nodi in cui c'e' un limite al numero di archi che un nodo puo' coprire. Il risultato e' completato con la dimostrazione di un limite inferiore sul rapporto di approssimazione che un qualsiasi algoritmo distribuito per il problema in questione puo' ottenere. La novita' ed originalita' del metodo e le potenzialita' che esso offre nello sviluppo di algoritmi distribuiti sono le principali ragioni che hanno motivato l'assegnazione del premio.


This topic: Commissioni/Scientifica > WebHome > PremioCommissioneScientifica > MotivazioneSozio06
Topic revision: r1 - 2006-10-10 - AlessandroMei
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback