Neste trabalho, objetivamos apresentar o Teorema de Alon e Naor, o qual afirma que existe um algoritmo de aproximação para a norma de corte de uma matriz qualquer, sendo que a garantia de desempenho desse algoritmo é a inversa da constante de Grothendieck. Introduzimos a norma de corte de uma matriz e exibimos algumas de suas propriedades. Uma delas é que a norma de corte é equivalente a uma outra norma, que é valor ótimo de um programa inteiro quadrático que pode ser relaxado por um programa semidefinido. Além do Teorema de Alon e Naor, construímos mais dois algoritmos de aproximação para a norma de corte. Ambos possuem garantia de desempenho inferior que a do Teorema de Alon e Naor, porém as técnicas que foram utilizadas para obter tais algoritmos são interessantes. Enunciamos a Desigualdade e Grothendieck reformulada por Lindenstrauss e Pelcýnski e mostramos uma cota superior para a constante de Grothendieck que se baseia no Argumento de Krivine. Finalmente, apresentamos três aplicações do Teorema de Alon e Naor: em corte máximo de um grafo; na versão algorítmica do Lema da Regularidade de Szemerédi; e no Teorema de Frieze e Kannan. / In this work, our objective is to present Alon and Naor\'s Theorem, which states that there exists an approximation algorithm for cut-norm of any matrix and that the approximations guarantee of the algorithm is the inverse of the Grothendieck\'s constant. We introduce the cut-norm of a matrix and we show some of its properties. One is that the cut-norm is equivalent of some other norm which is the optimum value of quadratic integer program which can be relaxed for a semidefinite program. Beyond Alon and Naor\'s Theorem, we construct two more approximation algorithm for cut-norm. The approximation guarantee of both is inferior to the Alon and Naor\'s Theorem, but the techniques for obtaining such algorithms is interesting. We show Grothendieck\'s Inequality reformulated by Lindenstrauss e Pelcýnski and we show an upper bound for the Grothendieck\'s constant which is based on Krivine\'s Argument. Furthermore, we show three applications of Alon and Naor\'s Theorem: Maximum cut of a graph, an algorithmic version of Szemerédi Regularity Lemma, and Frieze and Kannan\'s Theorem.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-26042019-042143 |
| Date | 17 July 2014 |
| Creators | Endo, Eric Ossami |
| Contributors | Kohayakawa, Yoshiharu |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | English |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0022 seconds