Het kleine Grothendieck probleem over de orthogonale groep. (The little Grothendieck problem over the orthogonal group)

Abstract

In de grafentheorie is het maximale snede probleem een bekend NP-hard probleem. Hiervoor is door Goemans en Williamson [GW95] een 0.878-benaderingsalgoritme gevonden gebaseerd op semidefiniet programmeren. Later zijn dezelfde technieken gebruikt om een benadering te vinden voor de oplossing van een algemener probleem genaamd het kleine Grothendieck probleem. In dit literatuuronderzoek worden deze problemen bestudeerd. Ook wordt er met name uitvoerig ingegaan op de uitbreiding: het kleine Grothendieck probleem over de orthogonale groep. Een van de overeenkomsten van deze problemen is dat er voor allemaal een benaderingsalgoritme is met een bepaalde benaderingsconstante. Deze algoritmen gebaseerd op het Goemans-Williamson algoritme zullen worden beschreven, zodat de overeenkomsten duidelijk worden. Het laatst genoemde probleem heeft toepassingen in de Procrustes analyse. De Procrustesproblemen in de wiskunde gaan over het vinden van orthogonale transformaties, zodat de afstand tussen de getransformeerde puntenwolken zo klein mogelijk is. Dit zou bijvoorbeeld gebruikt kunnen worden in de fotografie. Daar zal in deze scriptie een voorbeeld van worden bestudeerd en worden vergeleken met een andere methode gebaseerd op de methode van Schonemann [Sch66].