δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Τα πολύτοπα σε προβλήματα βελτιστοποίησης και δειγματοληψίας δίνονται συνήθως από μια έμμεση αναπαράσταση μέσω μιας μηχανής οracle. Η πιο βασική μηχανή oracle είναι ο έλεγχος μέλους σε πολύτοπα που μπορεί να απαντήσει στο αν ένα σημείο επερώτησης q βρίσκεται μέσα στο P ή όχι, και χρησιμοποιείται συχνά ως βάση για πιο σύνθετες μηχανές oracle, όπως η μηχανή oracle διαχωρισμού και η μηχανή oracle συνόρου. Σε αυτή τη δουλειά στοχεύουμε στο σχεδιασμό, στην υλοποίηση και στην ανάλυση αλγορίθμων για μια προσεγγιστική μηχανή oracle για τον έλεγχο μέλους σε πολύτοπα που δίνονται ως η τομή ημιχώρων σε υψηλή διάσταση, ανταλλάσσοντας ακρίβεια για ταχύτητα.
Προηγούμενες απόπειρες βασίζονταν σε κλασικές τεχνικές προσέγγισης πολυτόπων που έχουν όμως εκθετική εξάρτηση στη διάσταση και είναι ως εκ τούτου μη αποδοτικές σε υψηλή διάσταση. Αποδεικνύουμε μια ευθεία αναγωγή από το πρόβλημα του προσεγγιστικού έλεγχου μέλους σε πολύτοπα στο πρόβλημα του προσεγγιστικού πλησιέστερου γείτονα σε σημεία και αποκτούμε έτσι πολυωνυμικά, ως προς τη διάσταση, όρια στη πολυπλοκότητα, εκμεταλλευόμενοι πρόσφατη πρόοδο στη πολυπλοκότητα της αναζήτησης του πλησιέστερου γείτονα. Στη συνέχεια χρησιμοποιούμε τη νέα δομή για έλεγχο μέλους σε πολύτοπα για να αποκτήσουμε μια λύση για το oracle συνόρου σε υψηλή διάσταση. Τέλος, αναλύουμε τους αλγορίθμους μας πειραματικά και παραθέτουμε τα αποτελέσματα.
(EL)
Polytopes in optimization and sampling problems are usually given by implicit rep-
resentations through oracles. The most basic oracle is the polytope membership ora-
cle which can identify whether a query point q lies inside P or not and is often used
as the basis for more complex oracles, such as the separation oracle or the bound-
ary oracle. In this work we aim to design, implement and analyse algorithms for
approximating the membership oracle in polytopes given as the intersection of half-
spaces in high dimension, by trading exactness for efficiency. Previous approaches
were based on classic polytope approximation techniques which, however, have
complexity that scales exponentially in the dimension and are, thus, intractable in
high dimension. We establish a straightforward reduction from approximate poly-
tope membership to approximate nearest neighbor search among points and obtain
complexity bounds polynomial in the dimension, by exploiting recent progress in
the complexity of nearest neighbor search. We then employ this new membership
oracle to obtain a solution for the boundary oracle in high dimension. Lastly, we
evaluate our algorithms experimentally and report results.
(EN)
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού » Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
