1. Home page
  2. Search

Polytope Membership in High Dimension

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Polytope Membership in High Dimension
Αναγνωστόπουλος Ευάγγελος (EL)
Anagnostopoulos Evangelos (EN)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2017
Τα πολύτοπα σε προβλήματα βελτιστοποίησης και δειγματοληψίας δίνονται συνήθως από μια έμμεση αναπαράσταση μέσω μιας μηχανής ο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)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού » Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)