Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14745
Τίτλος: | O Γραμμικός Προγραμματισμός Και Εφαρμογές Αυτού Πάνω Στο Πρόβλημα Κάλυψης Συνόλων |
Συγγραφείς: | Νικόλαος Γ. Ματσάκης Αφράτη Φώτω |
Λέξεις κλειδιά: | linear programming set cover vertex cover primal-dual schema dual fitting (randomized) rounding half-integrality ip2 preprocessing |
Ημερομηνία έκδοσης: | 20-Νοε-2006 |
Περίληψη: | Η διπλωματική αυτή εργασία ασχολείται με αλγοριθμικές εφαρμογές του Γραμμικού Προγραμματισμού πάνω στο Πρόβλημα Κάλυψης Συνόλων (Set Cover Problem) καθώς και σε κάποιες ειδικές περιπτώσεις ή παραλλαγές αυτού, με κυριότερη εξ αυτών το Πρόβλημα Κάλυψης Κορυφών (Vertex Cover Problem). Αφού γίνεται εισαγωγή στη Θεωρία του Γραμμικού Προγραμματισμού, αναλύονται οι δύο μέθοδοι που χρησιμοποιούνται στη σχεδίαση Προσεγγιστικών Αλγορίθμων. Η πρώτη μέθοδος είναι το primal-dual schema, το οποίο σε γενικές γραμμές κατασκευάζει επαναληπτικά λύσεις για το πρωτεύον πρόγραμμα και το δυικό αυτού, δίνοντας καλούς αλγορίθμους από άποψη πολυπλοκότητας. Η δεύτερη μέθοδος είναι η μέθοδος rounding. Σε αυτήν την περίπτωση, πλην των άλλων, δίδεται έμφαση στη κατασκευή προσεγγιστικού αλγορίθμου πιθανοτικής υφής, με πολύ καλό προσεγγιστικό παράγοντα. Γίνεται, επίσης, διερεύνηση των ημιακέραιων λύσεων για το Πρόβλημα Κάλυψης Κορυφών αλλά και των ιδιοτήτων των προγραμμάτων της μορφής ΙΡ2. Ένα ακόμη κεφάλαιο αφιερώνεται στη μέθοδο dual fitting εκ της οποίας μπορούμε να εκμαιεύουμε σημαντικά αποτελέσματα για ήδη υπάρχοντες αλγορίθμους σε πολλές παραλλαγές του προβλήματος Set Cover, τις οποίες και αναφέρουμε στην εργασία. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14745 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Μέγεθος | Μορφότυπος | |
---|---|---|---|
DT2006-0266.doc | 817 kB | Microsoft Word | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.