Προσεγγιστικοί Αλγόριθμοι Και Προσεγγιστικά Σχήματα Για Ειδικές Περιπτώσεις Του Προβλήματος Του Πλανόδιου Πωλητή (traveling Salesman Problem)

Abstract

Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη προσεγγιστικών αλγορίθμων και προσεγγιστικών σχημάτων που επιλύουν σε πολυωνυμικό χρόνο κάποιες ειδικές περιπτώσεις του NP-coplete Προβλήματος του πλανόδιου πωλητή (Traveling Salesman Problem, TSP). Η εργασία ξεκινά με μια εισαγωγή στη θεωρία της πολυπλοκότητας, τη θεωρία γράφων και τους προσεγγιστικούς αλγορίθμους. Ορίζεται στη συνέχεια το πρόβλημα στη γενική του μορφή (general TSP), και ακολουθεί ο ορισμός του Metric TSP (MTSP), με παρουσίαση και ανάλυση προσεγγιστικών αλγορίθμων που το επιλύουν σε πολυωνυμικό χρόνο. Ακολουθεί η περίπτωση του Ευκλείδιου TSP (Euclidean TSP), για το οποίο δίνεται ένα πολυωνυμικό προσεγγιστικό σχήμα (PTAS). Η τελευταία περίπτωση που μελετάται είναι το (1,2)-TSP, για το οποίο δίνονται οι πιο σημαντικοί προσεγγιστικοί αλγόριθμοι, μεταξύ των οποίων και ένας πολύ πρόσφατος (2005). Η εργασία ολοκληρώνεται με την παράθεση κάποιων σημαντικών πρακτικών εφαρμογών του TSP.