Προβλήματα Ελαχιστοποίησης Λόγου Αθροίσματος Υποσυνόλων

Abstract

Στην παρούσα διπλωματική εργασία, παρουσιάζουμε το πρόβλημα \SSR\ το οποίο ορίζεται ως εξής: δεδομένου ενός συνόλου θετικών ακεραίων $Z$ πληθυκότητας $n$, να προσδιοριστεί εάν υπάρχουν δύο ξένα υποσύνολα του $Z$, των οποίων ο λόγος των αθροισμάτων τους είναι βέλτιστος. Το \SSR\ αποτελεί πρόβλημα βελτιστοποίησης και είναι στενά συνδεδεμένο με το \ESS, οριζόμενο ως εξής: δεδομένου ενός συνόλου θετικών ακεραίων $Z$ πληθυκότητας $n$, να προσδιοριστεί εάν υπάρχουν δύο ξένα υποσύνολα του $Z$, τα στοιχεία των οποίων αθροίζουν στην ίδια τιμή. Ακριβέστερα, στο \SSR\ θεωρούμε ότι δεν υπάρχουν ξένα υποσύνολα που να αθροίζονται στον ίδιο αριθμό, συνεπώς αναζητούμε αυτά τα ξένα υποσύνολα των οποίων ο λόγος είναι πιο κοντά στη μονάδα.

Εμπνεόμενοι από τεχνικές που χρησιμοποιούνται στις πιο σύγχρονες ερευνητικές δημοσιεύσεις για τα προβλήματα \SubS\ και \ESS\ ,καθώς και προσεγγιστικών σχημάτων που έχουν διαμορφωθεί για το \SSR\ ,τα οποία περιγράφουμε αναλυτικά στη παρούσα διπλωματική, παρουσιάζουμε ένα νέο προσεγγιστικό σχήμα (FPTAS) το οποίο επιτυγχάνει τη καλύτερη πολυπλοκότητα από τα προσεγγιστικά σχήματα που έχουν παρουσιαστεί μέχρι σήμερα. Πιο αναλυτικά, αποδεικνύουμε ότι για την πολυπλοκότητα του FPTAS για το \SSR\ εκφραζόμενη στη μορφή $O((n + \frac{1}{\varepsilon})^c)$, γίνεται με $c < 5$, αποτέλεσμα το οποίο αποτελεί βελτίωση συγκριτικά με όλα τα FPTAS's που έχουν δημοσιευτεί.

Επιπροσθέτως, μέσω του προσεγγιστικού σχήματος που παρουσιάζεται σε αυτή τη διπλωματική, αποδεικνύεται μια στενότερη σύνδεση μεταξύ της πολυπλοκότητας του \SSR\ και του \ASS\ .Ειδικότερα,στο προτεινόμενο FPTAS χρησιμοποιείται ως υπορουτίνα η προσεγγιστική επίλυση πολλών \SubS\ υποπροβλημάτων. Με αυτό τον τρόπο, οποιαδήποτε βελτίωση στην πολυπλοκότητα σε προσεγγιστικό σχήμα για το \SubS\ μπορεί να μεταφερθεί απευθείας και στο προσεγγιστικό σχήμα για το \SSR\.

Καταλήγουμε, ότι με το FPTAS που παρουσιάζουμε αποτυπώνεται η ανάγκη για περαιτέρω έρευνα στη προσεγγισιμότητα του \SubS\ και ειδικότερα η μελέτη μιας πιο αδύναμης μορφής προσέγγισης η οποία χαλαρώνει την ανισότητα για το άθροισμα στόχο $t$. Πιο αναλυτικά, για το σύνολο λύση $Y$ για το οποίο πρέπει να ισχύει $\Sigma(Y) \leq t$, η ανισότητα μετατρέπεται σε $\Sigma(Y) \leq (1 + \varepsilon) \cdot t$, συνθήκη η οποία δύναται να βοηθήσει στην διαμόρφωση κάποιου βελτιωμένου προσεγγιστικού σχήματος για το \SubS\ και επομένως για το \SSR\ που είναι το υπό μελέτη πρόβλημα.