Dado um digrafo $D$, uma subdivisão de $D$ é um digrafo obtido pela substituição de cada arco $uv$ em $D$ por um caminho direcionado $P(u,v)$ de $u$ para $v$ tal que todo vértice interno de $P(u,v)$ (caso exista) é um novo vértice. Em 1985, Mader conjecturou a existência de uma função $f$ tal que todo digrafo com grau mínimo de saída pelo menos $f(k)$ contém uma subdivisão do torneio transitivo de ordem $k$. Essa conjectura ainda está completamente aberta uma vez que mesmo a existência de $f(5)$ é desconhecida. Neste seminário, apresentaremos algumas novas evidências dessa conjectura. Mais precisamente, se $D$ é um caminho orientado, ou uma in-arborescência (i.e. uma árvore com todas arestas orientadas em direção a raiz), então todo digrafo com grau mínimo de saída suficientemente grande contém uma subdivisão de $D$. Ademais, apresentaremos uma visão geral das principais conjecturas e resultados da literatura relativos à subdivisão de digrafos.

We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items $I$ and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Prädel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.

We consider the Online Circle (resp. Sphere) Packing problem in which circles (resp. spheres) arrive one at a time and we need to pack them in unit square (resp. cube) bins with the goal of minimizing the total number of bins used. For circle packing, we improve the previous best-known competitive ratio for the bounded space version, when at most a constant number of bins can be open at any given time, from 2.439 to 2.3521 and we present an unbounded space algorithm of competitive ratio 2.3091. For sphere packing, we show a bounded space algorithm of competitive ratio 3.5316, an unbounded space algorithm of competitive ratio 3.5231, and a lower bound of 2.77 on the competitive ratio of any online bounded space algorithm.

A graph is planar if it can be drawn on the plane without edge crossings. Such a drawing is called an embedding on the plane.
This seminar will present a brief overview about graph planarity. I will go through the celebrated Kuratowski’s Theorem and a few more characterizations (Wagner’s, Tutte’s and Mac Lanes’) of planar graphs, some useful properties of planar graphs (Euler’s formula, Tutte’s embedding, etc.), planarity testing (Hopcroft-Tarjan, Boyer-Myrvold) and briefly mention a few generalizations of planarity (crossing number, genus, removal number, split number, etc.).

Nowadays, industries’ major concerns relate to faster reaction to customer needs and cost reduction in order to increase competitiveness. Both research and practice have shown that considering uncertainty and integrating different planning decisions can tackle those two concerns simultaneously. However, the increasing complexity of global supply chains trigged uncertainty sources and made it more difficult to coordinate production decisions (such as lot-sizing) with other hierarchical or supply chain stages decisions. One of the major hurdles in optimizing integrated planning decisions under uncertainty is to deliver high quality solutions with low computational effort. In this line, we aim to efficiently optimize integrated decisions of production lot-sizing with other decisions under various sources of uncertainty. Two research streams are fostered. The first focuses on the development of integrated lot-sizing mathematical programming models under uncertainty and on the comparison and assessment of the main advantages and limitations of each modeling approach. The second stream is on exact and hybrid solution approaches built on top of mathematical models that help solving large-scale integrated models.

Em um primeiro momento farei uma introdução à Teoria de Ramsey, onde serão apresentados resultados clássicos, tipos de problemas comuns na área e discutirei algumas técnicas comumente aplicadas na resolução dos problemas relacionados. Por fim, apresentarei um resultado recente envolvendo números de Ramsey para potências de caminhos. Mais especificamente, o número de Ramsey relativo a arestas de um grafo $H$ é definido como a menor quantidade de arestas $sr(H)$ tal que existe um grafo $G$ com $sr(H)$ arestas com a seguinte propriedade: toda coloração das arestas de $G$ com 2 cores contém uma cópia monocromática de $H$. Respondendo uma pergunta sugerida por Conlon, provamos que $sr(P_n^k)=O(n)$ para todo $k$ fixo, onde $P_n^k$ é a $k$-ésima potência do caminho com $n$ vértices $P_n$, i.e., o grafo com conjunto de vértices $V(P_n)$ e todas as arestas ${u,v}$ tais que a distância entre $u$ e $v$ em $P_n$ é no máximo $k$.
Obs: Não é preciso nenhum conhecimento de Teoria de Ramsey para o bom entendimento do seminário.
Os resultados que serão apresentados foram obtidos em conjunto com Clemens, Jenssen, Kohayakawa, Morrison, Reding e Roberts.

Uma decomposição por caminhos de um grafo $G$ é um conjunto de caminhos aresta-disjuntos de $G$ que cobre o conjunto de arestas de $G$. Gallai (1966) conjecturou que todo grafo simples com $n$ vértices admite uma decomposição por caminhos de tamanho no máximo $\frac{(n+1)}{2}$. A Conjectura de Gallai foi verificada para grafos nos quais todo circuito contém vértices de grau ímpar, para grafos Eulerianos com grau máximo 4, e algumas outras classes de grafos. Neste seminário estudaremos subgrafos redutores, uma técnica que nos permitiu verificar a Conjectura de Gallai para todos os grafos com grau máximo 4, e para grafos com treewidth no máximo 3. Além disso, nós podemos mostrar que os únicos grafos nessas classes que não admitem uma decomposição por caminhos de tamanho no máximo $n/2$ são isomorfos a $K_3$, $K_5$, ou $K_{5}-e$.

The genome median problem is an important problem in phylogenetic reconstruction under rearrangement models. It can be stated as follows: Given three genomes, find a fourth that minimizes the sum of the pairwise rearrangement distances between it and the three input genomes. In this paper, we model genomes as matrices and study the matrix median problem using the rank distance. It is known that, for any metric distance, at least one of the corners is a 4/3-approximation of the median. Our results allow us to compute up to three additional matrix median candidates, all of them with approximation ratios at least as good as the best corner, when the input matrices come from genomes. We also show a class of instances where our candidates are optimal. From the application point of view, it is usually more interesting to locate medians farther from the corners, and therefore, these new candidates are potentially more useful. In addition to the approximation algorithm, we suggest a heuristic to get a genome from an arbitrary square matrix. This is useful to translate the results of our median approximation algorithm back to genomes, and it has good results in our tests. To assess the relevance of our approach in the biological context, we ran simulated evolution tests and compared our solutions to those of an exact DCJ median solver. The results show that our method is capable of producing very good candidates.

The Multicommodity Connected Facility Location problem is a generalization of the Connected Facility Location problem, which arises from a combination of the Facility Location and the Steiner Forest problems through the rent-or-buy model. We consider the online version of this problem and present a randomized algorithm that is $O(\log^2 n)$-competitive, where $n$ is the number of given client pairs. Our algorithm combines the sample-and-augment framework with previous algorithms for the Online Prize-Collecting Facility Location and the Online Steiner Forest problems. Also, for the special case of the problem with edge scale factor equals 1, we show that a variant of our algorithm is deterministic and $O(\log n)$-competitive.

Interactive maps are maps that allow users to execute operations that alter the state of the visualization. Two of the most common operations are rotation and scaling. As one of these operations is executed, labels must maintain their size, shape and orientation. This may cause labels that were previously disjoint to overlap. For each label, we must determine a set of active ranges (i.e., intervals of angles or scales during which the label is visible) such that no pair of overlapping labels is ever active simultaneously. The objective is to maximize the total length of the active ranges of all labels. We prove a number of properties of optimal solutions which allow us to significantly reduce the size of an integer programming formulation from the literature. These properties are independent of the particular choice of operation, which makes our reduction techniques extremely flexible. We report the results of several experiments employing operations of rotation and scaling, and using two existing benchmarks with 180 real-world instances. We obtained reductions of over 100 times in the number of variables and constraints of the formulation, which led to a decrease of up to three orders of magnitude in running times.

Neste seminário serão apresentados alguns resultados obtidos sobre problemas de projeto de redes no modelo de otimização com leasing. Nos modelos de otimização tradicionais, geralmente pensamos que “compramos” os recursos que iremos utilizar para construir determinada infraestrutura, e que portanto esses recursos podem ser utilizados por tempo ilimitado. Em contrapartida, no modelo de otimização com leasing, supomos que cada recurso pode ser alugado por diferentes períodos finitos de tempo, com menor custo por unidade de tempo para períodos maiores. Esse modelo tem aplicação, por exemplo, na otimização de contratos em serviços de rede na nuvem, como Google App Engine, Amazon AWS e Microsoft Azure.
Na primeira parte do seminário será apresentado, para uma versão com leasing do problema connected facility location (CFL), um algoritmo que é uma 7,39-aproximação quando o fator de escala é 1. Será discutido também por que as técnicas de análise utilizadas na literatura para o CFL não permitem obter algoritmos com fator de aproximação constante para a versão com leasing quando o fator de escala é ilimitado. Os resultados podem ser estendidos para 3 outras variações do CFL, além das versões online dos 4 problemas propostos.
Na segunda parte do seminário, será apresentado o problema dos bilhetes de estacionamento (PP - parking permit problem), proposto por Meyerson (FOCS 2005), que pode ser utilizado para resolver a versão com leasing do problema da floresta de Steiner. Propomos uma generalização do PP com múltiplos bilhetes, inspirada na versão com leasing do problema da rede de Steiner. Serão apresentados algoritmos de aproximação e algoritmos online competitivos para esse problema, que podem ser utilizados para resolver o problema da rede de Steiner com leasing.
Os resultados foram obtidos em colaboração com Mário César San Felice e com o prof. Orlando Lee.

Neste seminário iremos apresentar o modelo de jogo de transportes proposto por Fotakis et al. [1] e discutir alguns dos resultados dos autores quanto à existência e ineficiência de equilíbrios (puros) de Nash deste jogo.

Referência(s):
[1] Fotakis, Dimitris, Laurent Gourvès, and Jérôme Monnot. “Selfish Transportation Games.” International Conference on Current Trends in Theory and Practice of Informatics. Springer, Cham, 2017.

Um vendedor tem um objeto para vender e deseja obter o maior valor possível por ele, porém não sabe o quanto os potenciais compradores estão dispostos a pagar. Um leilão parece uma maneira apropriada de vender este objeto. Conhecendo a distribuição das valorações dos compradores, qual é o mecanismo de leilão que maximiza o lucro esperado do vendedor? Em 1981 Roger Myerson demonstrou como construir um leilão que maximiza o lucro para uma ampla classe de problemas de leilão no artigo “Optimal Auction Design”, fundamental para a Teoria de Leilões. Esta teoria está na base dos leilões de anúncio utilizados hoje pelo Google e Facebook. Neste seminário iremos mostrar três resultados fundamentais da Teoria de Leilões tal como foram provados por Myerson, incluindo a construção de leilões ótimos.