Back to search

National and Kapodistrian University of Athens

Approximation Algorithms for the Precedence Constrained Minimum Knapsack and Capacitated Covering Integer Programs

Abstract

dc:description

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

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Σκαρλάτος Αντώνιος
  • Skarlatos Antonios

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, English, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:2940037

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Σκαρλάτος Αντώνιος; Skarlatos Antonios. Approximation Algorithms for the Precedence Constrained Minimum Knapsack and Capacitated Covering Integer Programs. 2021. https://pergamos.lib.uoa.gr/uoa/dl/object/2940037