Duas Barreiras para Programação Semidefinida
Autores
4067 |
303,920
|
|
4068 |
303,920
|
Informações:
Publicações do PESC
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.
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.