skip to main content
Idioma:

Aproximação da norma de corte via desigualdade de Grothendieck

Endo, Eric Ossami

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2014-07-17

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Aproximação da norma de corte via desigualdade de Grothendieck
  • Autor: Endo, Eric Ossami
  • Orientador: Kohayakawa, Yoshiharu
  • Assuntos: Algoritmos De Aproximação; Desigualdade De Grothendieck; Norma De Corte; Programa Semidefinido; Approximation Algorithm; Cut-Norm; Grothendieck'S Inequality; Semidefinite Programming
  • Notas: Dissertação (Mestrado)
  • Descrição: 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.
  • DOI: 10.11606/D.45.2019.tde-26042019-042143
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2014-07-17
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.