• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
Documento
Autor
Nombre completo
Eric Ossami Endo
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2014
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Proença, Rodrigo Bissacot
Título en portugués
Aproximação da norma de corte via desigualdade de Grothendieck
Palabras clave en portugués
Algoritmos de aproximação
Desigualdade de Grothendieck
Norma de corte
Programa semidefinido
Resumen en portugués
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.
Título en inglés
Approximation of the cut-norm via Grothendieck's inequality
Palabras clave en inglés
Approximation algorithm
Cut-norm
Grothendieck's inequality
Semidefinite programming
Resumen en inglés
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
mestrado_ENDO.pdf (683.45 Kbytes)
Fecha de Publicación
2019-05-03
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.