Abstract
dc:descriptionΤα πολύτοπα σε προβλήματα βελτιστοποίησης και δειγματοληψίας δίνονται συνήθως από μια έμμεση αναπαράσταση μέσω μιας μηχανής οracle. Η πιο βασική μηχανή oracle είναι ο έλεγχος μέλους σε πολύτοπα που μπορεί να απαντήσει στο αν ένα σημείο επερώτησης q βρίσκεται μέσα στο P ή όχι, και χρησιμοποιείται συχνά ως βάση για πιο σύνθετες μηχανές oracle, όπως η μηχανή oracle διαχωρισμού και η μηχανή oracle συνόρου. Σε αυτή τη δουλειά στοχεύουμε στο σχεδιασμό, στην υλοποίηση και στην ανάλυση αλγορίθμων για μια προσεγγιστική μηχανή oracle για τον έλεγχο μέλους σε πολύτοπα που δίνονται ως η τομή ημιχώρων σε υψηλή διάσταση, ανταλλάσσοντας ακρίβεια για ταχύτητα. Προηγούμενες απόπειρες βασίζονταν σε κλασικές τεχνικές προσέγγισης πολυτόπων που έχουν όμως εκθετική εξάρτηση στη διάσταση και είναι ως εκ τούτου μη αποδοτικές σε υψηλή διάσταση. Αποδεικνύουμε μια ευθεία αναγωγή από το πρόβλημα του προσεγγιστικού έλεγχου μέλους σε πολύτοπα στο πρόβλημα του προσεγγιστικού πλησιέστερου γείτονα σε σημεία και αποκτούμε έτσι πολυωνυμικά, ως προς τη διάσταση, όρια στη πολυπλοκότητα, εκμεταλλευόμενοι πρόσφατη πρόοδο στη πολυπλοκότητα της αναζήτησης του πλησιέστερου γείτονα. Στη συνέχεια χρησιμοποιούμε τη νέα δομή για έλεγχο μέλους σε πολύτοπα για να αποκτήσουμε μια λύση για το oracle συνόρου σε υψηλή διάσταση. Τέλος, αναλύουμε τους αλγορίθμους μας πειραματικά και παραθέτουμε τα αποτελέσματα.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Αναγνωστόπουλος Ευάγγελος
- Anagnostopoulos Evangelos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1672490