• 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
 
 
Mémoire de Maîtrise
DOI
Document
Auteur
Nom complet
Eric Ossami Endo
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2014
Directeur
Jury
Kohayakawa, Yoshiharu (Président)
Hoppen, Carlos
Proença, Rodrigo Bissacot
Titre en portugais
Aproximação da norma de corte via desigualdade de Grothendieck
Mots-clés en portugais
Algoritmos de aproximação
Desigualdade de Grothendieck
Norma de corte
Programa semidefinido
Resumé en portugais
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.
Titre en anglais
Approximation of the cut-norm via Grothendieck's inequality
Mots-clés en anglais
Approximation algorithm
Cut-norm
Grothendieck's inequality
Semidefinite programming
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
mestrado_ENDO.pdf (683.45 Kbytes)
Date de Publication
2019-05-03
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.