Eberhard Karls University of Tubingen¨
                          Faculty of Science
                     Department of Computer Science
             Bachelor Thesis in Computer Science
                 Is Ordinal Embedding NP-hard?
                          Margareta Schluter¨
                             Supervisor
                      Prof. Dr. Ulrike von Luxburg
                          Theory of Machine Learning
                        Department of Computer Science
                            Faculty of Science
                           University of Tubingen¨
                                 Schluter,¨        Margareta:
                                 Is Ordinal Embedding NP-hard?
                                 Bachelorthesis in Computer Science
                                 Eberhard Karls University of Tubingen¨
                                 Processing period: 01/04/2020 - 31/07/2020
             Abstract
             The task of ordinal embedding is to find points y ,...,y ∈ Rd that comply to
                                             1   n
             a given set of constraints. Each constraint is of the form “y is closer to y than
                                                   i       j
             to y ”. This thesis investigates the computational complexity of that problem.
                k
             Most important, it is proven that ordinal embedding is NP-hard for all dimen-
             sions d ≥ 2. More precise, it is shown that deciding whether such an embedding
             exists for a given constraint set is ∃R-complete. The proof is a reduction from
             d-Euclidean for preference profiles, a problem that is ∃R-complete according
             to Peters (2017). Besides, the thesis tries to deepen the understanding of solv-
             ing ordinal embedding with first order optimization methods. One approach
             is a statement by Bower et al. (2018), that in a two-dimensional search space,
             the used objective has no non-global minimizers. This claim is reconstructed
             and generalized by elimination of an unnecessary premise. If the statement
             holds for higher dimensions, it is a valuable result for the solving of ordinal
             embedding, since optimization algorithms are prone to convergence to local
             minima instead of global solutions.
                                      i
                         ii