Aproximação da norma de corte via desigualdade de Grothendieck (2014)
- Authors:
- Autor USP: ENDO, ERIC OSSAMI - IME
- Unidade: IME
- Sigla do Departamento: MAT
- DOI: 10.11606/D.45.2019.tde-26042019-042143
- 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
- Status:
- Artigo possui versão em acesso aberto em repositório (Green Open Access)
- Versão do Documento:
- Versão submetida (Pré-print)
- Acessar versão aberta:
-
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: https://teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143. Acesso em: 15 abr. 2026. -
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 https://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 2026 abr. 15 ] Available from: https://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 2026 abr. 15 ] Available from: https://teses.usp.br/teses/disponiveis/45/45131/tde-26042019-042143
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
