============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Desigualdades de  Grothendieck com  restrições 
             de posto
            
Palestrante: Fernando Mário de Oliveira Filho
             Institut für Mathematik
             Freie Universität Berlin

Hora e Data: 14h, sexta-feira, 9 de dezembro de 2011

Local:       auditório do NUMEC

Resumo:

Para inteiros r >= 1 e matrizes reais m x n, consideramos o
problema

SDP_r(A) = max{\sum_{i = 1}^m \sum_{j = 1}^n A_{ij}<x_i,y_j>: 
  	     	x_i, y_j \in S^{r-1} }

onde S^{r-1} é a  esfera (r-1)-dimensional (i.e., o conjunto
de vetores de comprimento 1 em R^r) e <x,y> denota o produto
interno euclideano.

Para  todo  r  >=  1,  este é  um  problema  de  programação
semidefinida com uma restrição  adicional de posto. Quando A
é  a  matriz laplaciana  de  um  grafo  o problema  SDP_1(A)
resume-se  ao   problema  do  corte  máximo   e  é  portanto
NP-difícil.  Na verdade, SDP_r(A)  é um  problema NP-difícil
para todo r >= 1.

Grothendieck  (1953)  provou  que,  para  qualquer  m,  n  e
qualquer matriz  real A com m  linhas e n  colunas, 

     SDP_{m +n}(A) <= K SDP_1(A),   

a  chamada "desigualdade  de Grothendieck".   

Mostrarei  como  generalizar  esse  resultado  para  r >= 1,
calculando  limitantes superiores  para a  constante  K para
todos os postos r >= 1.  A principal técnica utilizada é uma
generalização  do   método  de  arredondamento   através  de
hiperplanos aleatórios (utilizado,  por exemplo, por Goemans
e  Williamson  (1995)   para  desenvolver  um  algoritmo  de
aproximação para  o problema  do corte máximo),  que permite
obter uma solução de SDP_r(A) arredondando-se uma solução de
SDP_s(A), onde s >= r.

Trabalho em conjunto com J. Brïet e F. Vallentin.