Παρουσίαση Διπλωματικής εργασίας Ε.Αναγνωστόπουλου, 29/5/2017, ώρα 14:00, αίθουσα Α56
- Πέμπτη, 25 Μαΐου 2017 -
Τίτλος: Polytope Membership in High Dimension

Abstract:
Polytopes in optimization, volume and sampling problems are usually given by implicit representations through oracles. The most basic oracle is the
polytope membership oracle which can identify whether a query point lies inside the given polytope or not, and is often used as the basis for more
complex oracles, such as the separation oracle or the boundary oracle. In this work we aim to design, implement and analyze algorithms for
approximating the membership oracle in polytopes given as the intersection of halfspaces 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 polytope 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.