Busca avançada
Ano de início
Entree

Aproximabilidade de problemas de otimização em grafos

Processo: 98/02407-9
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de agosto de 1998
Vigência (Término): 31 de julho de 2002
Área do 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

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)