Aproximação da norma de corte via desigualdade de Grothendieck (2014)
- Authors:
- Autor USP: ENDO, ERIC OSSAMI - IME
- Unidade: IME
- Sigla do Departamento: MAT
- Subjects: COMBINATÓRIA; PROGRAMAÇÃO MATEMÁTICA
- Agências de fomento:
- Language: Português
- Abstract: Neste trabalho, objetivamos apresentar o Teorema de Alon a Noar, 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 é 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 umprograma 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 Noar: em corte máximo de um grafo; na versão algorítimica do Lema da Regularidade de Szemerédi; e no Teorema de Frieze e Kannan
- Imprenta:
- Data da defesa: 17.07.2014
-
ABNT
ENDO, Eric Ossami. Aproximação da norma de corte via desigualdade de Grothendieck. 2014. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2014. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143. Acesso em: 29 dez. 2025. -
APA
Endo, E. O. (2014). Aproximação da norma de corte via desigualdade de Grothendieck (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143 -
NLM
Endo EO. Aproximação da norma de corte via desigualdade de Grothendieck [Internet]. 2014 ;[citado 2025 dez. 29 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143 -
Vancouver
Endo EO. Aproximação da norma de corte via desigualdade de Grothendieck [Internet]. 2014 ;[citado 2025 dez. 29 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
