Prof. Carlos Martinhon -  IC/UFF

Palestras ministradas
a)  Título: Uma Introdução aos Algoritmos Randômicos
Resumo:  Ao executar um algoritmo determinístico repetidas vezes para uma mesma entrada, obtém-se  sempre, uma mesma saída com tempo de processamento sempre constante. Isto não ocorre, por exemplo, com os algoritmos randômicos ou probabilísticos onde cada execução poderá produzir (dependendo da aplicação) uma saída diferente baseada em eventos aleatórios. Nestas situações, os resultados obtidos e/ou os tempos de processamento definem uma “função randômica” da entrada. Surpreendentemente, para uma grande quantidade de problemas, a utilização de algoritmos randômicos se constitui na forma mais simples e/ou mais rápida de implementação! Nestes casos, sua utilização implica em uma melhora de desempenho quando comparada a algoritmos puramente determinísticos!
        Faremos, nesta exposição, uma breve introdução aos algoritmos randômicos discutindo, respectivamente, os métodos de Monte Carlos e Las Vegas. O método de Monte Carlo, será apresentado utilizando-se o algoritmo de Freidvals[1979] para multiplicação de matrizes (na sua versão decisão). No método de Las Vegas apresentaremos dois novos algoritmos (Arantes, França e Martinhon[2002]), para geração de orientações acíclicas em grafos. Mostraremos que, em ambos os casos, o tempo esperado de processamento será polinomial no tamanho da entrada.
          Locais: IC/UFF; IME/UERJ; Coppe/Sistemas[2002]; LNCC (2004).   (Tranparências)

 
b) Título: An Improved Derandomized Approximation Algorithm for the Max-Controlled Set Problem
Abstract: Given a graph G=(V,E) and a subset M of V, with |V|=n, the vertex v (beloning to V), is said to be controlled by M if the majority of v’s neighbors (including itself) belong to M. The set M defines a monopoly in G if M controls every vertex v beloning to V. In the Max-Controlled Set Problem (MCSP), two graphs G1=(V,E1) and G2=(V,E2) such that E1 (subset of E2), and M (subset of V) are given. The objective is to find a sandwich graph G=(V,E), where E1 is subset of E and E is a subset of E2, and such that the number of vertices of G controlled by M is maximized. Here, it is assumed a priori that there does not exist an edge set E as above such that M is a monopoly in G. Deciding whether there exists an edge set E such that M is a monopoly in G is polynomially time solvable. However, if such an E does not exist, maximizing the total number of controlled vertices by M is NP-hard.
    Through the use of randomized rounding and derandomization techniques, we present an improved deterministic polynomial time approximation for the MCSP. If |V| = n > 4, we guarantee a performance ratio equal to 1/2+[(1+n1/2)/(2n-2)] (the case n<=4 is solved exactly through a Parameterized algorithm). The derandomized algorithm for the MCSP is achieved through the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance.

Local: Coppe/Sistemas[2002].    (Slides PDF) 


c) Título: Randomized Approximation Algorithms
Resumo: A tremendous growth of randomized algorithms has been viewed during the last decade. Nowadays, we can find applications in many different areas of computer science. Essentially, randomized algorithms toss coins in order to make multi-way decisions. Surprisingly, this may produces the simplest algorithm available, or the fastest, or both. In other words, many problems that takes a long time to be solved on deterministic machines can often be solved very quickly on probabilistic machines. In this talk, a special attention is given to some applications in the combinatorial optimization area. The probabilistic techniques to NP-hard combinatorial problems deals essentially with randomized approximation algorithms. Some derandomization estrategies producing the deterministic counterpart is also presented. The derandomization technique is ilustrated by the method of conditional probabilities.
          Local:  Coppe/Produção[2003].
     
     
d) Título: Relax-and-Cut Aplicado ao Problema de Roteamento de Veículos.

Resumo:  Algumas técnicas de otimização combinatória visam a determinação do valor ótimo ou solução exata associada ao problema original. Quando aplicada a problemas computacionalmente difíceis (problemas NP-Árduos) o tempo de processamento cresce exponencialmente em função do tamanho do problema. Apesar disto, técnicas sofisticadas de otimização são adotadas buscando-se a solução exata de problemas combinatórios de tamanho cada vez maior.
    Apresentaremos uma técnica denominada Relax-and-Cut, que visa combinar relaxação lagrangeana e teoria poliédrica na solução do problema clássico de Roteamento de Veículos. São gerados bons limitantes inferiores e superiores para o ótimo do problema original. Estes valores são então utilizados na implementação de uma busca em árvore (Branch-and-Bound) para a determinação da solução exata do problema de Roteamento.

Local:  UFF[1999], Unicamp[1998]  (Transparências)   


e) Título: Redes Neurais e Otimização Combinatória.

Resumo: Nesta  apresentação  discutimos a utilização de  redes neurais artificiais na resolução de alguns dos problemas clássicos de otimização combinatória. Entre eles, abordamos o problema de  Programação Linear, Caminho Mínimo, Árvore Mínima de Steiner, Caixeiro Viajante, Mochila 0/1 e o Problema  das  Quatro Cores.
     Alguns casos,  são  resolvidos  através do  modelo de  Hopfield, enquanto que, em outros,  uma  topologia  da  rede associada é construída.

         Local:  UFJF[1995],  UFF[1998],  (Transparências)