Mapas de símbolos proporcionais são ferramentas cartográficas utilizadas para visualizar dados ou eventos associados a uma localização e uma intensidade. Neste trabalho, cada evento é representado por um disco opaco, cuja área é proporcional à intensidade registrada. Discos próximos podem se sobrepor, dificultando a determinação de seus tamanhos. O problema que abordamos consiste em computar a ordem na qual eles devem ser dispostos de forma a maximizar uma das seguintes métricas de qualidade: a borda visível total (Max-Total) e a menor borda visível de todos os discos (Max-Min). Estudamos três variantes deste problema, duas das quais são NP-difíceis e uma terceira cuja complexidade computacional está em aberto. Propomos um novo modelo de programação linear inteira e avaliamos seu desempenho através de uma série de experimentos com instâncias geradas a partir de dados reais. Os resultados mostram que nosso algoritmo reduz significativamente os tempos de execução quando comparado aos demais apresentados na literatura.

The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon. The AGP is a well known NP-hard problem and, for this reason, all algorithms proposed so far to solve it are unable to guarantee optimality except in especial cases. In our work, we developed a new method for solving the Art Gallery Problem by iteratively generating upper and lower bounds while seeking to reach an exact solution. Notwithstanding that convergence remains an important open question, our algorithm has been successfully tested on a very large collection of instances from publicly available benchmarks. The proposed algorithm showed a remarkable performance, obtaining provably optimal solutions for every instance in a matter of minutes on a standard desktop computer. To our knowledge, despite the AGP having been studied for four decades within the field of computational geometry, this is the first time that an exact algorithm is proposed and extensively tested for this problem.

O seminário servirá como preparação para uma palestra de uma conferência (SEA 2013) e será apresentado em inglês.

Nós descrevemos um algoritmo para subdividir uma triangulação arbitrária de uma superfície, produzindo uma nova triangulação que é 3-colorível nos vértices. (Triangulações 3-coloríveis podem ser representadas e manipulads eficientemente pela estrutura de dados Gema de Montagner e Stolfi.) A solução padrão para este problema é a subdivisão baricêntrica, que produz 6F triângulos, quando aplicada a uma triangulação com F triângulos. Nosso algoritmo produz uma subdivisão com no máximo 2F - Eb + 4 (2 - X) triângulos, onde X é a característica de Euler da superfície (2 para esfera, 1 para disco, 0 para o toro) e Eb é o número de arestas de fronteira da triangulação (arestas adjacentes a um único triângulo).

Gallai’s Conjecture states that any three longest paths in a connected graph have a vertex in common. It is known that the equivalent statement for two longest paths is true. There have been numerous research projects in the field, however, which investigated the case of three longest paths. One of the approaches usually taken is to limit the scope of the problem to specific classes of graphs. In the paper which will be presented, the authors prove that, for connected circular arc graphs and connected interval graphs, all longest paths have a common vertex.

Fulkerson’s Conjecture says that every bridgeless cubic graph has six perfect matchings such that every edge belongs to precisely two of them. In 1976, F. Loupekine created a method for constructing new snarks from already known ones. In the present work, we consider an infinite family of Loupekine’s snarks constructed from the Petersen Graph, and verify Fulkerson’s Conjecture for this family.

Consider the supply chain problem of minimizing ordering, distribution and inventory holding costs of a supply chain formed by a set of facilities and clients. On the one hand, network design problems usually aim at associating a facility to a given client; on the other hand, traditional inventory problem try to minimize inventory and ordering costs in a fixed network. Coordinating network and inventory decisions can represent significant economy for many applications. This work describes a generalization of the widely studied facility location problem (FLP) that integrates both decisions. We consider this problem when the instances satisfy assumptions such as a metric space and monotonic increasing inventory holding costs. In this talk, it is shown how to obtain a (2+1/e)-approximation by randomized rounding of the relaxation of a natural mixed integer formulation.

Two important characteristics encountered in many real-world scheduling problems are heterogeneous machines/processors and a certain degree of uncertainty about the actual sizes of jobs. The first characteristic entails machine dependent processing times of jobs and is captured by the classical unrelated machine scheduling model. The second characteristic is adequately addressed by stochastic processing times of jobs as they are studied in classical stochastic scheduling models. While there is an extensive but separate literature for the two scheduling models, we study for the first time a combined model that takes both characteristics into account simultaneously. Here, the processing time of job $j$ on machine $i$ is governed by random variable $P_{ij}$, and its actual realization becomes known only upon job completion. With $w_j$ being the given weight of job $j$, we study the classical objective to minimize the expected total weighted completion time. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee $3/2 + D$. Here, $D$ is an upper bound on the squared coefficient of variation of the processing times. We show that the dependence of the performance guarantee on $D$ is tight, as we obtain a $D/2$ lower bound for the type of policies that we use. When jobs also have individual release dates, our bound is $(2 + D)$. Via $D=0$, currently best known bounds for deterministic scheduling are contained as a special case.

O Andrei vai fazer basicamente a apresentação de alguns problemas do seu projeto de doutorado.

Neste seminário apresentarei meu projeto de iniciação sobre o Problema do Caixeiro Viajante com Coleta e Entrega, um problema semelhante ao tradicional Problema do Caixeiro Viajante, porém com restrições adicionais relativas à ordem em que os vértices devem ser visitados. Este problema é desafiante com relação ao tamanho das instâncias resolvidas pelos algoritmos atuais. Neste projeto foi implementado um algoritmo branch and cut para a sua resolução e os resultados são comparados com os resultados encontrados na literatura recente.

Nesse seminário apresentarei três resultados do artigo Dominating Cliques in Graphs, das autoras Margaret B. Cozzens e Laura L. Kelleher, publicado no Discrete Mathematics 86. O artigo trata do problema de conjuntos dominantes cliques e apresenta condições suficientes por meio de subgrafos proibidos para garantir a existência de um conjuntos clique dominantes em grafos conexos.

Em 1981 Tuza conjecturou: se um grafo simples $G$, não contém mais do que $k$ triângulos aresta-disjuntos, então existe um conjunto com no máximo $2k$ arestas que interceptam todos os triângulos de $G$. A conjectura permanece aberta por mais de trinta anos, porém para algumas classes de grafos ela foi verificada. Nesse seminário, apresentei a prova da conjectura para grafos planares e grafos sem subdivisões do $K_{3,3}$.

O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatória NP-difícil onde, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade limitada para atender a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere desse pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Uma formulação de programação linear inteira e aplicações para o OCARP são discutidas. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programação linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito os desvios entre limitantes e o número de melhores soluções.

Sejam $M$ um conjunto de $n$ homens e $W$ um conjunto de $n$ mulheres, onde cada indivíduo fornece uma lista ordenada de preferências que classifica um subconjunto de pessoas do sexo oposto. Um casamento $F$ é um subconjunto de $M \times W$ e se $(m, w) \in F$ então podemos escrever $F(m) = w$ e $F(w) = m$. Um par $(m, w) \notin F$, onde $m \in M$ e $w \in W$, é chamado de bloqueante se e somente se $m$ prefere $w$ a $F(m)$ e $w$ prefere $m$ a $F(w)$. Dizemos que $F$ é estável se e somente se $\bar{F}$ não contém um par bloqueante. O Problema do Casamento Estável com Empates e Listas Incompletas (SMTI) consiste em encontrar tal conjunto estável $F$. Sabe-se que toda instância do SMTI admite pelo menos um conjunto estável e que o problema de encontrar o conjunto estável de cardinalidade máxima (MAX-SMTI) é NP-dificil e APX-difícil. Neste seminário será abordado o algoritmo de 3/2-aproximação apresentado por Király [1], o melhor conhecido até o momento.

Referência(s):
[1] Király, Zoltán. Linear time local approximation algorithm for maximum stable marriage. Proceedings of MATCH-UP’12: the 2nd International Workshop on Matching Under Preferences, pages 99-110, 2012.

O número de cruzamentos de um grafo é o menor número de cruzamentos em todos os desenhos de um grafo.

Paul Turán propôs o problema de determinar o número de cruzamentos do $K_{m,n}$ após trabalhar em uma fábrica de tijolos na segunda guerra mundial. Logo após, Zarankiewicz apresentou uma construção que produz um desenho com $Z(m,n)= [m/2][(m-1)/2][n/2][(n-1)/2]$, tal que [n] indica a função piso, e argumentou que $cr(K_{m,n})=Z(m,n)$. Porém, sua prova continha um erro, transformando o seu resultado em uma conjectura. Ainda assim, ficou estabelecido que $cr(K_{3,n}) = Z(m,n)$. Kleitman provou a conjectura para $m$ ou $n$ menor ou igual a 6.

Este seminário abordará uma breve introdução ao problema de número de cruzamentos de um grafo. Em específico, apresentaremos resultados estabelecidos para o $K_{m,n}$, com $m$ ou $n$ menor ou igual a 6. O foco deste seminário são os resultados do artigo do D. J. Kleitman [1] sobre o $cr(K_{5,n})$.

Referência(s):
[1] Kleitman, Daniel J. “The crossing number of $K_{5,n}$.” Journal of Combinatorial Theory 9.4 (1970): 315-323.

Recentemente, Aros-Vera et al. [1] introduziram uma formulação de Programação Linear Inteira Mista (PLIM) para o problema de “Multinomial Logit Facility Location” e consideraram sua aplicação na alocação de estacionamentos próximos a estações de trem/metrô e terminais de ônibus, na qual o objetivo é maximizar a quantidade de usuários do transporte coletivo. A função objetivo considera é não-linear e o trabalho de Aros-Vera et al. [1] mostra como é possível obter uma formulação linear para o problema.

Neste seminário, apresentaremos um resumo de parte do artigo de Aros-Vera et al. [1] e os resultados que obtivemos para este problema em colaboração com o Eduardo Moreno e o Wilfredo Yushimito, ambos da Universidad Adolfo Ibañez, Santiago, Chile. Apresentaremos uma melhoria na formulação de Aros-Vera et al., uma nova formulação e um algoritmo de branch-and-bound para o problema. Resultados computacionais mostram que em muitos casos nosso algoritmo é literalmente mil vezes mais rápido do que a formulação de Aros-Vera et al.

Referência(s):
[1] (2013) p-Hub approach for the optimal park-and-ride facility location problem. Felipe Aros-Vera and Vladimir Marianov and John E. Mitchell. European Journal of Operational Research.

Nesse seminário apresentarei quatro resultados relacionados a cliques dominantes, em algumas classes de grafos. O primeiro deles é um resultado de El-Zahar e P. Erdos que garante a existência de $P_3$ ou uma Clique Dominante para a classe de grafos livres de $2K_2$ induzido. O segundo é um resultado de F.R.K. Chung, Gyárfás, Trotter e Tuza, que prova que os grafos livres de $2K_2$ induzido que possuem um $C_3$, tem o número de clique dominação igual ao número clique. Os dois últimos resultados são de G. Bacsó e Zs. Tuza. O primeiro caracteriza os grafos livres de $P_4$ induzido como sendo os grafos nos quais em todos os seus subgrafos conexos, todas as cliques maximais são dominantes. E o último é um resultado que prova que em um grafo qualquer, todos os seus subgrafos conexos possuem uma clique dominante se, e somente se, esse grafo é livre de $P_5$ e $C_5$ induzido.

Nesta apresentação é descrito o problema Online Connected Facility Location (OCFL), que é a versão online do Connected Facility Location (CFL). O CFL é uma combinação do problema Facility Location (FL) e do problema Steiner Tree (ST). Vamos apresentar um algoritmo probabilístico $O(\log_2 n)$-competitivo para o OCFL usando a técnica sample-and-augment e resultados anteriores para os problemas Online Facility Location (OFL) e Online Steiner Tree (OST).