Autores

4067
303,920
4068
303,920

Informações:

Publicações do PESC

Título
Duas Barreiras para Programação Semidefinida
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
7/12/2007
Resumo

A programação semidefinida tem recebido a atenção de vários pesquisadores nas últimas décadas. Em especial, por volta de 1995, com o trabalho de Goemans e Williansom [13], quando apresentaram uma heurística para o problema de corte máximo, baseada em um problema de programação semidefinida, que produz um corte com a garantia de estar a 14% da solução ótima. Neste trabalho, apresentamos duas novas metodologias para tratar problemas de programação semidefinida: o método de centros analíticos e a barreira hiper-cúbica. Associamos estes métodos a problemas de otimização combinatória, além de avaliá-los em relação aos melhores métodos existentes.

Abstract

The semidefinite programming has been receiving the attention of several researchers’ in the last decades. Especially, around the year of 1995 with the work of Goemans and Willianson [13], where they presented a heuristic for the max-cut problem, based on a semidefinite programming produces a cut with the guarantee of being to 14% of the optimal solution. In this work, we presented two new methodologies to treat problems of semidefinite programming : the method of analytic centers and the hiper-cubic barrier. We associate these methods to problems of combinatorial optimization, besides evaluating them in relation to the best existent methods.

Arquivo
Topo