Ανασκόπηση των τεχνικών γραμμικής διάταξης και διάταξης σε πολυδιάστατα πεδία

Abstract

Το πρόβλημα της ελάχιστης γραμμικής διάταξης είναι ένα κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης που έχει μελετηθεί για πολλά χρόνια. Στην παρούσα εργασία γίνεται για πρώτη φορά μία βιβλιογραφική ανασκόπηση του προβλήματος τέτοιου εύρους, η οποία έχει ως στόχο τη συγκεντρωτική παρουσίαση των πιο σημαντικών ερευνητικών ευρημάτων όλον αυτόν τον καιρό. Αρχικά, καταγράφεται η πρόοδος της πολυπλοκότητας όσον αφορά την προσέγγιση του προβλήματος στη γενική περίπτωση, αλλά και για συγκεκριμένες κατηγορίες γράφων. Έπειτα, καταγράφονται οι βασικότερες μέθοδοι υπολογισμού κατώτατων ορίων ανά τα χρόνια. Στη συνέχεια, παρουσιάζονται τόσο οι πιο παλιοί και απλοί όσο και οι πιο σύγχρονοι, αποδοτικοί και σύνθετοι προσεγγιστικοί αλγόριθμοι του προβλήματος. Έπειτα, διατυπώνεται η δομή κάποιων αλγορίθμων που υπολογίζουν τη βέλτιστη λύση σε πολυωνυμικό χρόνο για τις κατηγορίες γράφων τις οποίες αφορούν και καταγράφονται βιβλιογραφικά ευρήματα σχετικά με το πρόβλημα σε μεγαλύτερες διαστάσεις. Τέλος, η εργασία ολοκληρώνεται με μία σύνοψη των παραπάνω και αναφορές σε πιθανές μελλοντικές κατευθύνσεις του προβλήματος.