Προσεγγιστικοί αλγόριθμοι για το πρόβλημα του Knapsack με περιορισμό προτεραιότητας και για Ακέραια Προβλήματα Κάλυψης με χωρητικότητα.

Στην διπλωματική το κύριο πρόβλημα μελέτης είναι το πρόβλημα του knapsack και ειδικότερα μία γενίκευσή του στην οποία υπάρχει μία έννοια προτεραιότητας ως προς την επιλογή των αντικειμένων. Αρχικά παρουσιάζουμε το πρόβλημα του minimum knapsack με σκοπό να εισάγουμε κάποιες χρήσιμες τεχνικές με τις οποίες μπορούμε να κατασκευάσουμε primal-dual αλγορίθμους για το πρόβλημα. Ύστερα, εστιάζουμε την προσοχή μας στο γενικευμένο πρόβλημα precedence constrained minimum knapsack, το οποίο είναι παρόμοιο με το knapsack με τον επιπλέον περιορισμό ότι η επιλογή των αντικειμένων πρέπει να σέβεται μία έννοια  προτεραιότητας που ορίζεται μέσω μίας μερικής διάταξης. Για το πρόβλημα αυτό, μελετάμε κάποια γραμμικά προγράμματα μαζί με τις ιδιότητές τους. Ακόμα, κατασκευάζουμε έναν προσεγγιστικό αλγόριθμο στρογγυλοποίησης για το 0-1 PCKP και παρουσιάζουμε κάποια νέα αποτελέσματα για το PCKP για την περίπτωση που μπορούμε να διαλέξουμε κάποιο αντικείμενο και πάνω από μία φορά. Στο τέλος του PCKP κεφαλαίου, ένα ήδη γνωστό αποτέλεσμα κάτω φράγματος παρουσιάζεται με λίγο διαφορετικό τρόπο. Τέλος, μελετάμε τα capacitated covering ακέραια προγράμματος και εμπνευσμένοι από γνωστές τεχνικές, δίνουμε κάποια αποτελέσματα για την ειδική περίπτωση 0-1 CIP.