Back to search

National and Kapodistrian University of Athens

Polytope Membership in High Dimension

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 × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1672490

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Αναγνωστόπουλος Ευάγγελος; Anagnostopoulos Evangelos. Polytope Membership in High Dimension. 2017. https://pergamos.lib.uoa.gr/uoa/dl/object/1672490