Teoria x Prática: Será que vamos conseguir vencer?

Geraldo Robson Mateus (Universidade Federal de Minas Gerais)

A Teoria na prática tem tido uma forte demanda acadêmica, social e econômica. O objetivo desta palestra é mostrar como problemas clássicos podem ser integrados e explorados para gerar resultados na prática. Como motivação serão usados modelos, formulações e algoritmos para problemas de otimização de fluxos e alocação que fazem parte da literatura desde as origens da computação e podem atender a diversas aplicações. Estas surgem pela integração de problemas clássicos de fluxos em redes, planejamento da produção, sequenciamento, roteamento, localização de facilidades, recobrimento, coloração de grafos, conjuntos independentes e o próprio problema de alocação. Atendem a diversos critérios de otimização como custos, tempo, qualidade, e restrições relacionadas a atributos de capacidade, tempo, sequenciamento, disjunção. Com as alternativas recentes de formulações tem permitido gerar algoritmos eficientes e capazes de atender aos desafios das aplicações reais.

Grafos-(k, l) bem-cobertos

Sulamita Klein (Universidade Federal do Rio de Janeiro)

Um grafo G = (V,E) é (k,l) se o seu conjunto de vértices V pode ser particionado em k conjuntos independentes e l cliques. Brandstadt provou que o reconhecimento de grafos-(k, l) é polinomial para k ≤ 2 e l ≤ 2 e NP-completo caso contrário. G é bem coberto quando todos os seus conjuntos independentes maximais têm o mesmo número de vértices. Chvátal e Slater mostraram que o reconhecimento de grafos bem cobertos em geral é coNP-completo. Entretanto, existem reconhecimentos polinomiais para algumas classes de grafos: bipartidos, split, cografos entre outras. O problema de decisão (k, l)-BEM- COBERTO ((k, l)WCG) tem como entrada um grafo G = (V, E) e a questão: G é um grafo-(k, l) e um grafo bem coberto? Vamos discutir a complexidade desse problema.

Esse trabalho foi feito em colaboração com Luerbio Faria e Sancrey Rodrigues Alves.

Selfish 2D Bin Packing Games

Yoshiko Wakabayashi (Universidade de São Paulo)

We address a game-theoretical version of the well-known bin packing problem, selfish bin packing problem. In the bin packing problem, one is given a set of items and wishes to pack them into a minimum number of bins. The more commonly investigated variants are those in which the items and the bins have similar shape: for example, in the 2D (resp. 3D) bin packing, the items and bins are rectangles (resp. boxes). The selfish 1D bin packing problem has been investigated since 2006. We investigate a 2D version, in which the items to be packed are rectangles, the bins are unit squares, and the packing must be orthogonal. This game starts with a set of items arbitrarily packed in bins. The cost of an item is defined as the ratio between its area and the total occupied area of the respective bin. Each item is a selfish player that wants to minimize its cost. A migration of an item to another bin is allowed only when its cost is decreased. We show that this game always converges to a Nash equilibrium (a stable packing where no item can reduce its cost by moving to a different bin). Our focus is the study of the price of anarchy of this game, which is the ratio between the worst cost of a Nash equilibrium and the optimal social cost (the minimum number of bins needed to pack the given items). We show that the price of anarchy of this game is unbounded; so we address the particular case where all items are squares, and show that, in this case, it is at least 2.3634 and at most 2.6875. We also mention some results we have obtained for d-dimensional cubes, d>2. For the 2D version, when all items are squares, we also present some recent results on the strong price of anarchy. For this case, instead of Nash equilibrium, we consider strong Nash equilibrium (a stable packing in which no set of items can simultaneously migrate to another bin and decrease the cost of each item in the set).

This is joint work with C.G. Fernandes (USP), C.E. Ferreira (USP) and F.K. Miyazawa (UNICAMP).

Geometria Molecular: Modelos e Algoritmos em 5D

Carlile Lavor (Universidade Estadual de Campinas)

Discutiremos um novo modelo para representar a estrutura geométrica de uma molécula em 5 dimensões, utilizando o Espaço Conforme e uma linguagem mais poderosa do que a Álgebra Linear: a Álgebra Geométrica. O Modelo Conforme pode ser visto como uma extensão do Modelo Projetivo, muito utilizado em Geometria Computacional. A Álgebra Geométrica é uma área da Matemática que busca representações algébricas para conceitos geométricos. Reconhecida pela comunidade dos físicos como ferramenta de grande importância, vem ganhando espaço em outras áreas, como estrutura molecular, visualização de dados, computação gráfica, visão computacional e robótica. A beleza e o poder da Álgebra Geométrica estão relacionados à sua capacidade de unificação, simplificação e generalização de vários objetos da Matemática que envolvem conceitos geométricos (por exemplo, vetores, matrizes, números complexos e quatérnios podem todos ser vistos de uma maneira integrada). Tudo isso será exemplificado com um problema real de grande importância em biologia computacional: calcular a estrutura 3D de uma molécula de proteína usando distâncias entre átomos próximos.