Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14745
Title: | O Γραμμικός Προγραμματισμός Και Εφαρμογές Αυτού Πάνω Στο Πρόβλημα Κάλυψης Συνόλων |
Authors: | Νικόλαος Γ. Ματσάκης Αφράτη Φώτω |
Keywords: | linear programming set cover vertex cover primal-dual schema dual fitting (randomized) rounding half-integrality ip2 preprocessing |
Issue Date: | 20-Nov-2006 |
Abstract: | Η διπλωματική αυτή εργασία ασχολείται με αλγοριθμικές εφαρμογές του Γραμμικού Προγραμματισμού πάνω στο Πρόβλημα Κάλυψης Συνόλων (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 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2006-0266.doc | 817 kB | Microsoft Word | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.