| Processo: | 98/02407-9 |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Data de Início da vigência: | 01 de agosto de 1998 |
| Data de Término da vigência: | 31 de julho de 2002 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação |
| Pesquisador responsável: | Yoshiko Wakabayashi |
| Beneficiário: | Liliane Rose Benning Salgado |
| 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: | 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios, AP.TEM |
| Assunto(s): | Algoritmos de aproximação Combinatória Grafos aleatórios |
| Palavra(s)-Chave do Pesquisador: | Algoritmos De Aproximacao | Combinatoria | Complexidade | Grafos | Otimizacao |
Resumo Estudo da aproximabilidade de alguns problemas de otimização NP-difíceis sobre grafos ou outras estruturas discretas. Temos interesse na analise e no desenvolvimento de melhores algoritmos de aproximação, e em questões relativas ao grau de aproximabilidade ou não-aproximabilidade dos problemas. Dentre os problemas que serão objeto de nosso estudo mencionamos o problema do balance máximo, o problema dos K-centros e problemas sobre grafos com certa conectividade de vértices. Além do interesse em problemas específicos, esperamos também pesquisar questões mais gerais relativas às classes de aproximação e busca de técnicas que se generalizam para uma gama maior de problemas. (AU) | |
| 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) | |