| Processo: | 13/20740-9 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de janeiro de 2014 |
| Data de Término da vigência: | 31 de agosto de 2014 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Yoshiko Wakabayashi |
| Beneficiário: | Marcel Kenji de Carli Silva |
| Instituição Sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Vinculado ao auxílio: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM |
| Assunto(s): | Otimização combinatória Combinatória poliédrica |
| Palavra(s)-Chave do Pesquisador: | Combinatória Poliédrica | Espectraedro | Função teta de Lovász | Programação semidefinida | Otimização Combinatória |
Resumo O foco deste projeto é o desenvolvimento de ferramentas de Programação Semidefinida e Análise Convexa para aplicação em Otimização Combinatória, visando generalizar a abordagem da Combinatória Poliédrica. Estamos interessados na estrutura facial de relaxações semidefinidas para certos problemas combinatórios e sua correspondência com propriedades combinatórias dos problemas em questão. Como subproduto, esperamos aprofundar nossa compreensão sobre o ganho real de formulações semidefinidas que lhe tornam tão superiores a formulações lineares para certos problemas, e potencialmente replicar esse sucesso para novos problemas.A maioria dos resultados existentes nessa linha de pesquisa envolve o objeto central conhecido como corpo teta de um grafo, a partir do qual se define a função teta de Lovász. A teoria em torno desses objetos é muito rica e elegante, e também se aplica ao programa semidefinido utilizado por Goemans e Williamson em seu famoso algoritmo de aproximação para o problema do corte máximo. Descrevemos algumas direções de pesquisa envolvendo a estrutura facial desses objetos e das respectivas condições de otimalidade, bem como avenidas mais amplas de pesquisa com o objetivo de determinar o real poder de formulações semidefinidas em Otimização Combinatória e em geral. | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |