Άπληστοι Αλγόριθμοι για Ανάθεση Εργασιών σε Ομάδες με Κοινωνικές Προτιμήσεις

Abstract

Στα πλαίσια αυτής της εργασίας μελετάμε το πρόβλημα Team Formation amidst Conflicts, ένα πρόβλημα ανάθεσης εργασιών σε ομάδες. Στόχος του προβλήματος είναι να αντιστοιχίσουμε ένα σύνολο φοιτητών σε εργασίες, τηρώντας τις χωρητικότητες των εργασιών και μεγιστοποιώντας τον βαθμό ικανοποίησης των φοιτητών τόσο από την εργασία που τους ανατέθηκε όσο και από τους συνεργάτες τους. Στο πρώτο και θεωρητικό μέρος της διπλωματικής επικεντρωνόμαστε στον άπληστο αλγόριθμο για το πρόβλημα, ο οποίος παρουσιάζει πολύ καλή επίδοση στα πειράματα αλλά έχει λόγο προσέγγισης της τάξης του 1/n (όπου n το πλήθος των φοιτητών), με στόχο να κατανοήσουμε σε τι οφείλεται η καλή του επίδοση. Αποδεικνύουμε ότι για πολύ μεγάλες χωρητικότητες ο αλγόριθμος πετυχαίνει λόγο προσέγγισης 1/m, όπου m το πλήθος των εργασιών, ενώ για μια ειδική περίπτωση συσχετιζόμενων ομάδων παρουσιάζει λόγο προσέγγισης καλύτερο του 1/3. Τέλος, ολοκληρώνουμε τα ευρήματά μας με ένα πειραματικό μέρος, στο οποίο συγκρίνουμε την επίδοση του άπληστου αλγορίθμου με άλλους αλγορίθμους για το πρόβλημα, εκτελώντας τους με είσοδο τυχαία παραγόμενα συσχετιζόμενα δεδομένα.