Aproximação da norma de corte via desigualdade de Grothendieck
| Autor: | Endo, Eric Ossami |
|---|---|
| Jazyk: | portugalština |
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Dissertação de Mestrado |
| Popis: | 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|