mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2016 » Maria Petropanagiotaki Anonymously browsing from 54.80.26.116 at 07:23:51, 25-09-2017. login
download defense details: { pdf }

MSc thesis defense presentation

Maria Petropanagiotaki defends her MSc thesis.

Date: Friday, 04 Nov 2016
Time: 12:00-13:00
Location: Univeristy of Athens, Department of Mathematics, University of Athens, room A11
Thesis title: Παραμετρικοί Αλγόριθμοι και Μητροειδή η χρήση των συνόλων αντιπροσώπευσης
Committee:

Thesis abstract

Έστω 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-ΜΟΝΟΠΑΤΙ.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.