O Γραμμικός Προγραμματισμός Και Εφαρμογές Αυτού Πάνω Στο Πρόβλημα Κάλυψης Συνόλων

Abstract

Η διπλωματική αυτή εργασία ασχολείται με αλγοριθμικές εφαρμογές του Γραμμικού Προγραμματισμού πάνω στο Πρόβλημα Κάλυψης Συνόλων (Set Cover Problem) καθώς και σε κάποιες ειδικές περιπτώσεις ή παραλλαγές αυτού, με κυριότερη εξ αυτών το Πρόβλημα Κάλυψης Κορυφών (Vertex Cover Problem). Αφού γίνεται εισαγωγή στη Θεωρία του Γραμμικού Προγραμματισμού, αναλύονται οι δύο μέθοδοι που χρησιμοποιούνται στη σχεδίαση Προσεγγιστικών Αλγορίθμων. Η πρώτη μέθοδος είναι το primal-dual schema, το οποίο σε γενικές γραμμές κατασκευάζει επαναληπτικά λύσεις για το πρωτεύον πρόγραμμα και το δυικό αυτού, δίνοντας καλούς αλγορίθμους από άποψη πολυπλοκότητας. Η δεύτερη μέθοδος είναι η μέθοδος rounding. Σε αυτήν την περίπτωση, πλην των άλλων, δίδεται έμφαση στη κατασκευή προσεγγιστικού αλγορίθμου πιθανοτικής υφής, με πολύ καλό προσεγγιστικό παράγοντα. Γίνεται, επίσης, διερεύνηση των ημιακέραιων λύσεων για το Πρόβλημα Κάλυψης Κορυφών αλλά και των ιδιοτήτων των προγραμμάτων της μορφής ΙΡ2. Ένα ακόμη κεφάλαιο αφιερώνεται στη μέθοδο dual fitting εκ της οποίας μπορούμε να εκμαιεύουμε σημαντικά αποτελέσματα για ήδη υπάρχοντες αλγορίθμους σε πολλές παραλλαγές του προβλήματος Set Cover, τις οποίες και αναφέρουμε στην εργασία.