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 SizeFormat 
DT2006-0266.doc817 kBMicrosoft WordView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.