Μονάδα:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-12-09
Συγγραφέας:
Πετροπαναγιωτάκη Μαρία
Στοιχεία επιβλεπόντων καθηγητών:
Θηλυκός Δημήτριος, Επίκουρος Καθηγητής Τμήματος Μαθηματικών, Ε.Κ.Π.Α.
Κολλίοπουλος Σταύρος, αναπληρωτής καθηγητής τμήματος Πληροφορικής και Τηλεπικοινωνιών
Κυρούσης Ελευθέριος, καθηγητής τμήματος Μαθηματικών, Ε.Κ.Π.Α.
Πρωτότυπος Τίτλος:
Παραμετρικοί Αλγόριθμοι και Μητροειδή: η χρήση των συνόλων αντιπροσώπευσης
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Παραμετρικοί Αλγόριθμοι και Μητροειδή: η χρήση των συνόλων αντιπροσώπευσης
Περίληψη:
Έστω M = (E,I) μητροειδές και S = {S1,...,St} οικογένεια υποσυνόλων του E με |Si| = p
∀i ∈ {1, . . . , t}. Μια υποοικογένεια S′ ⊆ S ονομάζεται q-αντιπροσωπευτική της S, αν για κάθε σύνολο
της οικογένειας S που μπορεί να επεκταθεί σε μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του q
νέα στοιχεία υπάρχει και κάποιο σύνολο της υποοικογένειας S′, το οποίο μπορεί να επεκταθεί σε
μεγαλύτερο ανεξάρτητο σύνολο προσθέτοντας του τα ίδια q στοιχεία. Από το Θεώρημα Δύο Οικογενειών
του Bollobás και τη γενικευσή του σε διανυσματικούς χώρους από τον Lovász, προκύπτει ότι υπάρχει
q-αντιπροσωπευτική οικογένεια με το πολύ (p+q) ανά p σύνολα.
Σε αυτήν την εργασία, δίνουμε δύο αλγορίθμους για την κατασκευή αντιπροσωπευτικής οικογένειας μεγέθους (p+q) ανά p. Ο πρώτος αλγόριθμος αφορά τα γραμμικά μητροειδή και «αλγοριθμοποιεί» την από-
δειξη του Lovász κατασκευάζοντας οικογένεια σε χρόνο πολυωνυμικό ως προς (p+q) ανά p, t και τον χρόνο
που απαιτείται για την πραγματοποίηση μιας πράξης σε κάποιο σώμα F. Ο δεύτερος αφορά μόνο τα ομοιόμορφα μητροειδή και τρέχει σε O((1 − x)^{−q} · 2^{o(p+q)} · t · log n) χρόνο.
Στη συνέχεια, δείχνουμε πως υπολογίζοντας αποδοτικά αντιπροσωπευτικές οικογένειες, μπορούμε να κατασκευάσουμε γρήγορους παραμετρικούς αλγορίθμους για τα ακόλουθα προβλήματα: ΤΟΜΗ l-ΜΗΤΡΟΕΙΔΩΝ, ΜΑΚΡΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΣ ΚΥΚΛΟΣ και k-ΜΟΝΟΠΑΤΙ.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
σύνολα αντιπροσώπευσης, παραμετρικοί αλγόριθμοι, μητροειδή, ΤΟΜΗ l-ΜΗΤΡΟΕΙΔΩΝ, ΜΑΚΡΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΣ ΚΥΚΛΟΣ, k-ΜΟΝΟΠΑΤΙ.
Αρ. σελίδων ευρετηρίου:
1
Αρ. βιβλιογραφικών αναφορών:
37
