voltarData: 26/09/2018
Título: Uma condição de suficiência para o problema da quase-bipartição em grafos de distância-hereditária
Palestrante: Vinícius Gusmão, UFRJ
Data: 26 de setembro de 2018, 13 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.
Resumo: Jogos online para muitos jogadores, conhecidos como MMO (massive multiplayer online games), são boa fonte de problemas computacionais interessantes. A grande quantidade de jogadores simultâneos, produzindo enorme quantidade de informação a cada instante, somadas à exigência de baixíssima latência no processamento (para que a experiência do jogador não seja degradada por um retardo perceptível nos movimentos e ações), faz com que os jogos MMO tenham na eficiência de seus algoritmos um ponto crucial para sua existência. Em uma arquitetura cliente-servidor, que é bastante comum, na qual cada jogador transmite e recebe dados de um ou mais computadores (os servidores do jogo) mas não diretamente de outros jogadores, é preciso também orquestrar o funcionamento de diversas máquinas em cooperação para que se possa escalar livremente o número suportado de jogadores simultâneos.
Veremos alguns problemas interessantes que aparecem nesse tipo de ambiente, e focaremos no problema de se encontrar a melhor distribuição dos jogadores pelos servidores disponíveis, de forma a minimizar a troca de informação necessária entre os servidores do jogo sem contudo sobrecarregar qualquer um deles. Proporemos um algoritmo randomizado que, surpreendentemente, é o melhor que conhecemos para resolver o problema proposto, e faz uso -- talvez de forma didática -- dos celebrados filtros de Bloom.