Αλγόριθμοι Τοπικού Υπολογισμού Και Εφαρμογές Τους

Abstract

Τα τελευταια χρονια παρατηρειται το φαινομενο τα συνολα δεδομενων που δινονται ως εισοδοι σε αλγοριθμους προς επεξεργασια να ειναι ασυλληπτα μεγαλα. Λογικο ειναι, λοιπον, ο χρονος που θα κανει ο αλγοριθμος να τα επεξεργαστει να ειναι εξισου πολυς. Πολλες φορες, ομως, χρειαζομαστε τα αποτελεσματα σε συντομο χρονικο διαστημα ωστε να παρουμε αμεσα καποια αποφαση. Γι' αυτο και το ενδιαφερον εχει στραφει πλεον προς τους αλγοριθμους που τρεχουν σε υπογραμμικο χρονο σε σχεση με το μεγεθος της εισοδου. Στην περιπτωση που δεν μας ενδιαφερει ολοκληρη η λυση του προβληματος, αλλα αρκουμαστε σε ενα μικρο μερος αυτης καθε φορα, μπορουμε να χρησιμοποιησουμε εναν αλγοριθμο τοπικου υπολογισμου οι οποιοι παρουσιαζονται στην εργασια αυτη. Παρουσιαζονται δυο παραλληλοι αλγοριθμοι που τρεχουν σε υπογραμμικο χρονο. Στη συνεχεια δινονται αλγοριθμοι τοπικου υπολογισμου για αρκετα σημαντικα γραφοθεωρητικα προβληματα που βασιζονται στους προηγουμενους, και συγκεκριμενα για τα προβληματα του maximal independent set, του 2-χρωματισμου υπεργραφου και του maximal matching. Συζητουνται, επισης, εφαρμογες αυτου του ειδους αλγοριθμων σε διαφορες περιοχες της Επιστημης Υπολογιστων, οπως ο Σχεδιασμος Μηχανισμων και το Probabilistic Inference.