O cérebro humano possivelmente é a entidade organizada mais complexa da natureza. Apesar de mais de um século de intensos estudos científicos, pouco se sabe sobre sua estrutura e funcionamento. Nesta palestra vou procurar dar uma idéia da extensão dessa ignorância, em várias dimensões.
Esta palestra está inserida em um projeto FAPESP sobre técnicas matemáticas para estudo do cérebro (CEPID NEUROMAT) coordenado pelo prof. Antonio Galves do IME-USP.

Seja $D$ um digrafo. Uma partição em caminhos $P = {p_1, p_2, \ldots, p_n}$ de $D$ é uma coleção de caminhos de $D$ disjuntos nos vértices tal que $\cup_{p \in P} V(p) = V(D)$. A $k$-norma de uma partição em caminhos $P$ é $|P|_k = \sum_{p \in P} min(|V(p)|, k)$, onde $k$ é um inteiro positivo. Uma partição em caminhos $P$ é $k$-ótima se não existe uma partição em caminhos $P’$ de $D$ tal que $|P’|_k < |P|_k$. A conjectura de Berge afirma que se $P$ é uma partição em caminhos $k$-ótima, então existe $k$ conjuntos independentes disjuntos em $D$ que são ortogonais a $P$. Neste seminário, nós iremos discutir o resultado obtido por Dávid Herskovics, que demostra a validade da conjectura quando $k \geq \lambda - 3$.

Neste seminário será apresentado o trabalho de Seeun Umboh (SODA’15), em que se utiliza a técnica de aproximação de métricas finitas por métricas em árvores (Bartal, FOCS’96; Fakcharoenphol et al., 2004, JCSC) para projetar e analisar algoritmos para problemas online de projeto de redes. Ao invés de, como proposto por Bartal e feito tradicionalmente, simplesmente projetar um algoritmo $\alpha$-competitivo para árvores e utilizar o resultado de Fakcharoenphol et al. para obter um algoritmo probabilístico $O(\alpha \lg |V|)$-competitivo, onde $|V|$ é o tamanho da métrica, Umboh mostra como utilizar o conceito de decomposições hierárquicas para projetar algoritmos gulosos e, provando que um algoritmo é $\alpha$-competitivo para HSTs, como é possível provar que esse mesmo algoritmo é $O(\alpha \lg n)$-competitivo para métricas arbitrárias, sendo $n$ o número de requisições; assim, além de obter um fator de competitividade que não depende do tamanho da métrica, os algoritmos obtidos são determinísticos. No seminário serão apresentados os conceitos gerais de HSTs, decomposições hierárquicas e aproximação de métricas, e a aplicação da técnica de Umboh na análise do clássico algoritmo guloso para o problema da árvore de Steiner online.

A confiabilidade em redes de energia elétrica é uma característica valorizada por usuários e monitorada pelos órgãos reguladores. Uma maneira de aprimorar a confiabilidade de uma rede elétrica consiste na alocação de chaves de seccionamento, que têm por finalidade o isolamento de eventuais falhas na rede. Neste seminário será discutido um problema de alocação ótima de chaves em redes de distribuição de energia. Serão apresentados um modelo linear inteiro misto e um conjunto de desigualdades válidas fortes. Em seguida, será feita uma avaliação da aplicação das formulações propostas para a alocação ótima de chaves em um conjunto de redes de distribuição reais.

Online problems allow us to capture the uncertainty related to input data that arrives over time. This characteristic is common in problems from several areas of operations research and computer science, like:
-Dynamic data structures: the list access problem deals with the maintenance of linked lists.
-Computer architecture: the paging problem deals with the management of cache and random access memories.
-Sustainability: the ski-rental and parking permit problems are useful to manage energy consumption in computer clusters and multi-core processors.
-Network design: online versions of Steiner tree and facility location problems deal with building infrastructures to serve demands that arrive in real time.

In this seminar I will give an introduction to the area of online computation through the perspective of competitive analysis by showing some important examples in this field.

Um algoritmo genético de chaves aleatórias viciadas (biased random-key genetic algorithm – BRKGA) é uma meta-heurística evolutiva para problemas de otimização baseada no algoritmo de chaves aleatórias. Neste seminário será apresentado uma introdução ao BRKGA. Em seguida, será apresentado através de um exemplo uma API para o BRKGA disponibilizada por Rodrigo F. Toso e Mauricio G. C. Resende.

No Problema do Empacotamento de Círculos, dado um conjunto de círculos desejamos empacotar tais círculos em recipientes quadrados idênticos, isto é, posicionar os círculos dentro dos recipientes de forma que os círculos não se intersectem nem intersectem as bordas do recipientes, com o objetivo de minimizar o número de recipientes utilizados.
Neste seminário, apresentamos um artigo de Hokama, Miyazawa e Schouery[1] que apresenta um algoritmo 2,4394-competitivo para a versão onde os círculos chegam um-a-um sendo que quando um círculo chega ele precisa ser imediatamente empacotado e após empacotado o círculo não pode mais ser movido (a dita versão online do problema). Tal algoritmo tem espaço limitado, isto é, ele mantém apenas um número constante de recipientes abertos ao mesmo tempo, sendo que após um recipiente ser fechado ele não é reaberto e nem recebe novos círculos. Apresentamos também um limitante inferior de 2,2920 na razão de competitividade de qualquer algoritmo online com espaço limitado para tal problema.

Referência(s):
[1] Pedro Hokama, Flávio K. Miyazawa, Rafael C. S. Schouery. A bounded space algorithm for online circle packing. Information Processing Letters, 116:337-342, 2016.

No seminário será apresentado um protocolo combinando função fisicamente não clonável (PUF) com protocolos para acordo autenticado de chaves baseado em senhas (PAKE). O protocolo resultante da combinação fornece autenticação mútua multifator (PUF e senha) entre o cliente e servidor e estabelece uma chave de sessão entre as partes autenticadas. Tais características são muito importantes para esse tipo de protocolo e não foram encontradas juntas na literatura de autenticação baseada em PUF. É fornecida uma adaptação à combinação para que ela possa suportar senhas de pânico, que permite notificar o servidor em caso de alguma emergência, como ser coagido a digitar a senha. Além do mais, é proposto um novo protocolo multifator para autenticação de transação. Ele garante que apenas as partes autenticadas, na sessão atual, podem realizar transações bancárias válidas.

No seminário será apresentado um resumo do trabalho de Takuma e Yanagisawa (2013), onde uma estrutura de dados chamada cardinality filter foi proposta para fornecer de maneira eficiente um limite superior para o tamanho da interseção entre conjuntos. Durante o seminário algumas estrutura de dados para fornecer o tamanho exato da interseção entre conjuntos e um limite superior serão exemplificadas, tais estruturas de dados podem ser encontradas nos trabalhos de Bloom (1970) e Ding e König (2011). Por fim, será apresentado o uso do limite superior para o tamanho da interseção entre conjuntos para reduzir o tempo de processamento do algoritmo top-k query.

No seminário será apresentado o trabalho apresentado no artigo de Erdoğan e Miller-Hooks (2012), o qual apresenta o problema de roteamento de veículos denominado “Green Vehicle Routing Problem” (G-VRP), uma variação do clássico “Vehicle Routing Problem” (VRP), em que se considera veículos movidos a combustíveis limpos. Sendo o artigo seminal do problema, os autores apresentam uma formulação matemática e duas heurísticas para resolvê-lo, uma baseada na heurística de Clarke and Wright Savings e a outra é o Algoritmo de Clusterização Baseado em Densidade. Além disso, são apresentadas duas heurísticas de aprimoramento de solução baseadas em troca de vértices. Os métodos de solução são comparados em instâncias de tamanho pequeno e real, com uma análise em distância percorrida, número de veículos utilizados e número de clientes atendidos. Com isso, temos uma ideia dos ganhos e perdas da adaptação de uma frota de veículos para utilizarem combustíveis limpos.

O artigo “A Robust Method for the VRPTW with Multi-Start Simulated Annealing and Statistical Analysis (2007)” apresenta uma variação do Problema de Roteamento de Veículos, o VRPTW (Vehicle Routing Problem with Time Windows), onde uma janela de tempo determinada pelo cliente específica quando ele pode receber o bem ou serviço. Nessa variação do problema o objetivo do autor é encontrar a menor distância total possível para atender a todos os clientes respeitando a carga máxima dos veículos da frota e a janela de tempo dos clientes. O artigo propõem um método híbrido que utiliza as heurísticas Simulated Annealing e Hill Climbing, combinadas em um processo de reinicialização aleatória para obter melhores resultados. O trabalho apresenta alguns resultados melhores que os encontrados na literatura para as instâncias propostas por Solomon, ele apresenta os resultados obtidos pelo método e por outros autores para efeito de comparação. Ao fim, uma análise estatística é feita nos paramentos de configuração do sistema híbrido para determinar a melhor configuração do método.

Seja $G = (V, E)$ um grafo arbitrário e $w:E \rightarrow R$ uma função peso, e uma coloração dos vértices de $G$, induzida por $w$, definida como a soma dos pesos das arestas incidentes em $v$, para todo $v \in V(G)$. Neste trabalho, mostramos que decidir se um grafo possui uma rotulação $w$ das arestas em ${0, 1}$ e ${1, 2}$ que induz uma coloração própria é NP-Completo. Mostramos também que decidir se um grafo cúbico possui uma rotulação $w$ das arestas em ${a, b}$, para $a$ e $b$ racionais, que induz uma coloração própria é NP-Completo.

Recentemente, criptografia baseada em reticulados tem se tornado um tópico importante na comunidade criptográfica. Entre as razões para isso é o fato de que alguns problemas difíceis sobre reticulados tem a propriedade especial de permitir reduções de pior caso. Isso significa que pode ser provado que sistemas criptográficos são seguros na média baseado na suposição que alguns problema em reticulado é difícil no pior caso. Em outras palavras, nós podemos gerar parâmetros e chaves para nosso esquema criptográfico usando uma determinada distribuição probabilística de tal forma que qualquer adversário que quebrar a segurança do esquema pode ser usado como caixa preta para resolver qualquer instância de um certo problema em reticulados. Outro importante fator é que a criptografia baseada em reticulados podem resistir a ataques feitos por computadores quânticos, ou seja, ela faz parte da criptografia pós-quântica.

We consider the Geometric Firefighter Problem (GFP) recently proposed by Klein et al., where several variants of the problem were proven NP-hard. Despite this negative result, the design of algorithms for the GFP remains relevant as they may help reveal geometric properties of exact solutions. This paper proposes a method for finding guaranteed optimal solutions and reports on empirical tests over 900 polygons of up to 300 vertices. Almost all benchmark instances were solved within three minutes of CPU time on a standard off-the-shelf computer. This was made possible by a savvy combination of geometric preprocessing, integer programming modeling and heuristics.

No Problema de Empacotamento em Recipientes com Restrições de Classe, dados inteiros $B$ e $C$, e um conjunto de itens onde cada item $i$ possui um tamanho $s_i$ e uma classe $c_i$, o objetivo é empacotar todos os itens utilizando a menor quantidade de recipientes de capacidade $B$ possível, de forma que o número de classes diferentes empacotada em cada recipiente seja no máximo $C$. Neste seminário, apresentaremos algoritmos exatos baseados no método de Branch-and-Price para este problema, assim como algoritmos para o Problema da Mochila com Restrições de Classe, que aparece em nossos algoritmos como um subproblema a ser resolvido.

The crossing number of a graph $G$ is the least number of crossing of all possible drawings of $G$ in the plane. In this talk, we provide a structural characterization of all graphs with 1 crossing.

Na biologia molecular, o alinhamento de sequências é uma ferramenta para caracterizar similaridade ou distância entre sequências. Porções conservadas de proteínas são chamadas de motivos, domínios ou padrões e são descritas por expressões regulares. Um conjunto importante de motivos é definido pelo PROSITE. O problema do alinhamento de duas sequências restrito por expressão regular é o problema de encontrar o alinhamento ótimo entre duas cadeias $s$ e $t$ onde uma subcadeia de $s$ que pertence à linguagem da expressão regular está alinhada a uma subcadeia de $t$ que também pertence à linguagem da expressão regular. Neste trabalho, apresentamos uma forma de construir expressões regulares equivalentes a padrões PROSITE e uma forma de gerar efree-NFAs mais compactos que melhoraram o desempenho das soluções para o alinhamento restrito na literatura.

Dado um grafo $G = (V, E)$ não direcionado e não ponderado, considere que um fogo se inicia em um subconjunto de vértices do grafo, denominados focos de incêndio. O fogo se propaga em $G$ de forma iterativa. A cada iteração, $D$ vértices podem ser protegidos contra o fogo, o qual se espalha para todos os vértices desprotegidos pertencentes à vizinhança de algum vértice queimado. Um vértice queimado ou defendido na iteração atual, se mantém assim nas iterações posteriores. As iterações encerram-se quando o fogo não puder mais se espalhar. Neste contexto, o problema do firefighter consiste em minimizar a quantidade de vértices queimados, o qual foi proposto por Bert L. Hartnell em 1995. Este problema encontra aplicação no mundo real em situações em que se deseja, por exemplo, conter o espalhamento de incêndios, de doenças ou de vı́rus de computadores em uma rede. Trabalhos anteriores mostraram que este problema é NP-completo. Esse seminário tem por objetivo apresentar o trabalho intitulado: “The firefighter problem: Empirical results on random graphs” (García-Martínez et al., 2015) no qual são apresentadas técnicas de Programação Linear e Inteira e heurísticas para resolução do problema, aplicando-se tais abordagens em instâncias constituídas por grafos gerados aleatoriamente.

Nós estudamos jogos de localização de facilidades com capacidades, onde jogadores controlam terminais e necessitam conectar cada terminal a uma facilidade escolhida entre um conjunto de possíveis locais. Existem custos de abertura e restrições de capacidade para cada facilidade, além de custos fixos de conexão entre terminais e facilidades. Este problema possui diversas aplicações, especialmente em cenários distribuídos, onde uma autoridade central é muito cara ou mesmo impossível de existir. Neste artigo, procuramos analisar e apresentar novos resultados sobre a existência de equilíbrios Nash, Preço da Anarquia (PoA), e estabilidade (PoS), tanto para as versões métricas quanto não métricas deste jogo. Provamos que o PoA e PoS podem ser arbitrariamente grandes para algumas versões do jogo, mesmo quando versões seqüenciais são consideradas. Para variantes métricas, provamos que quando sequencialidade é assumida tanto o PoA quanto PoS tem limite superior na ordem de $2^k$ (sendo $k$ o número de jogadores).

O problema de roteamento em arcos capacitado e aberto (Open Capacitated Arc Routing Problem, OCARP) é um problema NP-difícil de otimização combinatória da classe de roteamento em arcos. Dado um grafo não-direcionado $G(V,E)$ e funções de custo e demanda associadas a cada aresta em $E$, o problema consiste em encontrar um conjunto de rotas de menor custo com capacidade limitada que atenda às demandas das arestas. As rotas no OCARP não são restritas a ciclos (podem iniciar e terminar em qualquer nó). Nesta apresentação mostraremos uma meta-heurística de Algoritmo Genético para o problema e uma formulação relaxada de Programação Linear Inteira para obter limitantes duais. Finalmente, serão apresentados os resultados com instâncias da literatura.

Em uma árvore enraizada não consideramos sua raiz como folha. Dados um grafo $G$ conexo e um inteiro $k$, no problema da $k$-floresta queremos encontrar uma floresta geradora $F$ de $G$ com número máximo de folhas tal que $F$ tenha no máximo $k$ árvores enraizadas. Neste seminário, vamos apresentar o problema da $k$-floresta, a relação dele com outros dois problemas e um algoritmo aproximado para o aquele problema.

Given two $k$-graphs ($k$-uniform hypergraphs) $H$ and $F$, a perfect $F$-packing in $H$ is a collection of vertex disjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$-packing is simply a perfect matching. For a given fixed $F$, it is often the case that the decision problem whether an $n$-vertex $k$-graph $H$ contains a perfect $F$-packing is NP-complete. Indeed, if $k \ge 3$, the corresponding problem for perfect matchings is NP-complete whilst if $k = 2$ the problem is NP-complete in the case when $F$ has a component consisting of at least $3$ vertices. There has been interest in determining the best possible degree condition that forces a perfect $F$-packing in $H$. From the complexity point of view, if such a condition is satisfied by $H$, then the decision problem is trivially in P: the answer is always positive. Then a natural question that arises from this is: can we lower the degree condition and still guarantee that the decision problem is polynomial-time solvable? In this talk I will discuss this problem and a recent general theorem developed for problems of this type.

Em 2008, Rahman e coautores apresentaram limitantes para a distância de rearranjo considerando permutações sem sinais e um modelo de rearranjo com eventos de reversão e transposição. Ainda como contribuição, foi apresentado um algoritmo $2k$-aproximado para o problema, onde $k$ é o fator de aproximação do algoritmo utilizado para decomposição de ciclos. Nesta apresentação será explicado o problema, bem como o funcionamento do algoritmo e seu fator de aproximação.

Neste seminário, apresentaremos o trabalho intitulado: The Firefighter Problem: Application of Hybrid Ant Colony Optimization Algorithms (Blum et al., 2014), no qual é apresentada uma abordagem para solucionar o Problema do Firefighter utilizando uma heurística baseada no comportamento de colônia de formigas, em conjunto com uma hibridização dessa técnica com um resolvedor de programação linear e inteira. O Problema do Firefighter: Dado um grafo $G = (V, E)$ não direcionado e não ponderado, considere que um fogo se inicia em um subconjunto de vértices do grafo, denominados focos de incêndio. O fogo se propaga em $G$ de forma iterativa. A cada iteração, $D$ vértices podem ser protegidos contra o fogo, o qual se espalha para todos os vértices desprotegidos pertencentes à vizinhança de algum vértice queimado. Um vértice queimado ou defendido na iteração atual, se mantém assim nas iterações posteriores. As iterações encerram-se quando o fogo não puder mais se espalhar. Neste contexto, o Problema do Firefighter, proposto por Bert L. Hartnell em 1995, consiste em minimizar a quantidade de vértices queimados. Este problema encontra aplicação no mundo real em situações em que se deseja, por exemplo, conter o espalhamento de incêndios, de doenças ou de vı́rus de computadores em uma rede. Trabalhos anteriores mostraram que este problema é NP-completo.

O problema de roteamento em arcos capacitado (do inglês, Capacitated Arc Routing Problem - CARP) trata-se de um problema de otimização combinatória NP-difícil da classe de roteamento em arcos. O CARP consiste em encontrar um conjunto de rotas de custo mínimo que atenda às demandas das arestas de um grafo, onde as rotas são sujeitas a restrições de capacidade.Neste seminário apresentaremos um método branch-and-cut proposto por Martinelli et al. (2013) que trabalha com a separação exata de duas classes de desigualdades válidas. Serão apresentados experimentos computacionais que demonstram a eficiência do método em gerar bons limitantes inferiores para o CARP em comparação com outros métodos do estado da arte.

We study a dynamic labeling problem on rotating maps, i.e., maps that allow for continuous rotations. As the map is rotated, labels must remain horizontally aligned. Rotations may cause labels that were previously disjoint to overlap. For each label, we must determine a set of active ranges (i.e., angular ranges during which the label is visible) such that at any rotation angle all active labels are disjoint. The objective is to maximize the sum of the angular length of all active ranges. We prove a number of properties of optimal solutions that allow us to significantly reduce the size of an integer programming model previously reported in the literature. We present the results of several experiments using two existing benchmarks with 180 real-world instances. We obtained reductions of over 100 times on the number of variables and constraints of the model. The compact formulation solved all but 5 instances to optimality in under a minute.