Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Author:
Anagnostopoulos Evangelos
Supervisors info:
Ιωάννης Εμίρης, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Δημήτρης Γουνόπουλος, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Βασίλης Ζησιμόπουλος, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Polytope Membership in High Dimension
Translated title:
Polytope Membership in High Dimension
Summary:
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.
Main subject category:
Science
Other subject categories:
Algorithms and Theory of Computation
Keywords:
polytope,high dimension,membership oracle,boundary oracle,approximate polytope membership,approximate polytope boundary
