Αλγόριθμοι Εμπνευσμένοι Από Το Τοπικό Λήμμα Του Lovasz (algorithms Inspired By The Lovasz Local Lemma)

Abstract

Σκοπός της διπλωματικής αυτής εργασίας είναι η μελέτη, η ανάλυση και η σχεδίασηπιθανοτικών αλγορίθμων τοπικής αναζήτησης για διακριτά προβλήματα περιορισμώνμε μεθόδους και τεχνικές που χρησιμοποιήθηκαν για την αλγοριθμική απόδειξη του"Lovasz Local Lemma". Συγκεκριμένα, θεωρούμε αλγορίθμους της εξής μορφής:- Αρχισε από μία τυχαία ανάθεση τιμών στις μεταβλητές του προβλήματος περιο-ρισμών.- Οσο υπάρχουν διαψευδούμενοι περιορισμοί, χρησιμοποίησε μια τυχαιοκρατικήδιαδικασία για να διαλέξεις έναν διαψευδούμενο περιορισμό c καθώς και νέεςτιμές για τις μεταβλητές τουΤόσο για την επιλογή του περιορισμού c όσο και για την επιλογή των τιμών στιςμεταβλητές του, υπάρχει πληθώρα ευρεστικών, αλλά όχι πολλά για να τις διαφορο-ποιήσουν πέρα από πειράματα. Στο paper του R. Moser για την κατασκευαστικήαπόδειξη του Lovasz Local Lemma στο STOC ’09 η επιλογή του c είναι αυθαίρετηενώ η επιλογή της ανάθεσης τιμών στις μεταβλητές γίνεται τυχαία και ομοιόρφα. Οτερματισμός του αλγορίθμου αποδεικνύεται δείχνοντας ότι μη τερματισμός θα σήμαινεκαθολική κωδικοποίηση ( universal compression ). Τόσο στη δουλειά του Moser όσοκαι στις μετέπειτα δουλειές, μια βασική απαίτηση είναι ότι θα πρέπει να υπάρχει έναπιθανοτικό μέτρο - γινόμενο (product measure) επί των μεταβλητών του προβλήματοςέτσι ώστε κάθε φορά που επαναδειγματοληπτούμε τις μεταβλητές ενός περιορισμο-ύ, οι τιμές που θα τις αναθέσουμε θα πρέπει να προκύπτουν μέσω ( της προβολήςτου) πιθανοτικού μέτρου ( στις μεταβλητές του περιορισμού). Αυτό έρχεται σε έντονηαντίθεση με τους αλγορίθμους της πράξης στους οποίους οι τιμές που δίνουμε στιςμεταβλητές εξαρτώνται από το πώς ο περιορισμός για τις μεταβλητές του οποίου δια-λέγουμε τιμές συσχετίζεται με τους γείτονές του, τόσο στατικά ( από τις μεταβλητέςπου μοιράζονται), όσο και " δυναμικά", δηλαδή από την τωρινή "κατάσταση" αυτώντων περιορισμών.Στην παρούσα διπλωματική δείχνουμε μία μέθοδο για να απαλλαχθεί κανείς από αυ-τή την απαίτηση. Συγκεκριμένα, δείχνουμε ότι η μέθοδος του Moser, δηλαδή το ναφράξουμε τον αριθμό των πιθανών άκαρπων τροχιών του αλγορίθμου χρησιμοποιών-τας ιδιότητες της εισόδου, για παράδειγμα το μέγιστο βαθμό του γράφου εξάρτησης,παραμένει πλήρως λειτουργική ακόμα και με την απουσία ενός πιθανοτικού μέτρου,δηλαδή όταν κάθε περιορισμός επιτρέπεται να αλλάξει τις μεταβλητές του με έναν "ιδιωτικό " τρόπο και στην πραγματικότητα, λαμβάνοντας υπόψιν τις τρέχουσες τιμέςτων μεταβλητών των γειτονικών περιορισμών. Επιπρόσθετα, παρατείθενται ορισμέναβιβλιογραφικά στοιχεία αναφορικά με τις αλγοριθμικές επεκτάσεις του Lovasz LocalLemma και μερικές αποδείξεις/ βελτιώσεις υπάρχοντων αποτελεσμάτων χρησιμποιών-τας την "εντροπική μέθοδο " του R. Moser.