Προσεγγιστικοί αλγόριθμοι για προβλήματα επιλογής πολλαπλών υποσυνόλων - Μελισσινός, Νικόλαος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών. Τομέας Μαθηματικών, 2018)
Πολλές φορές η απάντηση που θέλουμε σε μια ερώτηση δεν είναι ναι ή όχι. Υπάρχουν προβλήματα στα οποία αναζητούμε την βέλτιστη λύση και όχι απλά μια λύση. Δυστυχώς, δεν είναι πάντα εύκολη η εύρεση τέτοιων λύσεων. Κάποιες φορές η πολυπλοκότητα των προβλημάτων είναι τέτοια που δεν μας συμφέρει να περιμένουμε να βρούμε τη βέλτιστη λύση οπότε επιδιώκουμε την εύρεση μίας λιγότερο καλής την οποία θα μπορούσαμε να βρούμε αρκετά ποιο γρήγορα. Γιαυτό τον λόγο έχουν αναπτυχθεί προσεγγιστικοί αλγόριθμοι. Ένα πρόβλημα για το οποίο υπάρχουν τέτοιοι αλγόριθμοι είναι το Subset-sums ratio problem (πρόβλημα βελ- τιστοποίησης, αντίστοιχο του προβλήματος απόφασης ESS). Θα δούμε παρακάτω και άλλα αντίστοιχα προβλήματα και θα αναπτύξουμε FPTAS αλγορίθμους για τη προσέγγισή τους. Οι αλγόριθμοι που θα δούμε περιέχουν τεχνικές δυναμικού προ- γραμματισμού αλλά και τεχνικές που μετατρέπουν ψευδοπολυωνυμικού χρόνου αλγορίθμους σε πολυωνυμικού χρόνου προσεγγιστικούς αλγορίθμους. Επιπλέον θα αναφερθούμε σε κάποιες συνθήκες οι οποίες μας εξασφαλίζουν ύπαρξη FPTAS αλγορίθμων σε μια αρκετά γενική κατηγορία προβλημάτων επιλογής υποσυνόλων.