• 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
 
 
Master's Dissertation
DOI
Document
Author
Full name
Eric Ossami Endo
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2014
Supervisor
Committee
Kohayakawa, Yoshiharu (President)
Hoppen, Carlos
Proença, Rodrigo Bissacot
Title in Portuguese
Aproximação da norma de corte via desigualdade de Grothendieck
Keywords in Portuguese
Algoritmos de aproximação
Desigualdade de Grothendieck
Norma de corte
Programa semidefinido
Abstract in Portuguese
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.
Title in English
Approximation of the cut-norm via Grothendieck's inequality
Keywords in English
Approximation algorithm
Cut-norm
Grothendieck's inequality
Semidefinite programming
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
mestrado_ENDO.pdf (683.45 Kbytes)
Publishing Date
2019-05-03
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.