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

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].

Subject

Procrustes
little grothendieck
orthogonal
Grothendieck
little
kleine
probleem
orthogonale
groep
globale
registratie
correlatie
clusteren
benaderingsalgoritme
constante

To reference this document use:

http://resolver.tudelft.nl/uuid:7f9b1c16-4535-4b79-81bb-f569a758512c

Part of collection

Student theses

Document type

bachelor thesis

Rights

Files

PDF

bachelorscriptieKishanKal ... charan.pdf

2.54 MB

Close viewer