Nesta palestra vamos mostrar um algoritmo para encontrar uma base splines de peso total ótimo. Embora o problema verse sobre aproximação de funções, o algoritmo é essencialmente combinatório, um exemplo simples de otimização “gulosa”. O algoritmo é exponencial no pior caso, mas $O(n^4)$ (ou menos) para muitos casos de interesse prático.

Este trabalho é parte do projeto de doutorado de Ana Paula Resende Malheiro.

A família de problemas de Survivable Network Design trata da construção de redes que apresentam alguma garantia de conectividade na presença de falhas. Mais formalmente, exigimos que na rede resultante alguns pares de vértices $i,j$ sejam ligados por $r(i,j)$ caminhos disjuntos nas arestas.

Nesta palestra consideramos a versão online do problema, onde as restrições de conectividade $r(i,j)$ chegam em sequência e o algoritmo online deve escolher quais arestas acrescentar ao grafo (em construção) para atendê-las.

Descreveremos um resultado do artigo “Online and Stochastic Survivable Network Design” de Gupta, Krishnaswamy e Ravi, em que os autores apresentam um algoritmo $O(r_{max} \log^{3}n)$-competitivo para o problema, onde $r_{max}=\max r(i,j)$ e $n$ é o número de vértices do grafo.

Duas técnicas usadas no algoritmo merecem destaque: a ideia de imersão de redes em árvores com “distorção” pequena e o uso de um algoritmo online para o problema de Hitting Set como uma subrotina.

Mapas de símbolos proporcionais são uma ferramenta cartográfica para visualização de dados associados a eventos que têm localização e intensidade conhecidas. Para cada um desses eventos, dispõem-se símbolos sobre suas localizações, escalados de tal forma que sua área seja proporcional à intensidade do evento. Em nosso projeto, nos restringimos a mapas em que os símbolos são discos opacos. Devido à proximidade entre eles, podem ocorrer sobreposições. Se considerarmos um empilhamento de tais discos, partes de alguns deles poderão ficar encobertas pelos que estiverem sobre eles. Dependendo da ordem dos discos na pilha, o mapa pode passar maior ou menor informação visual. Embora a qualidade de um empilhamento seja um conceito subjetivo, foram definidas métricas para associá-la a valores numéricos, como, por exemplo, a soma do comprimento visível das bordas dos discos. Nosso trabalho enfoca no problema de encontrar um empilhamento que maximize essa soma. Até este momento, não é conhecido nenhum algoritmo polinomial para esse problema e, por isso, o resolvemos através de programação linear inteira.

Nesta palestra, apresentaremos o modelo de programação linear inteira utilizado, descrevendo também o estudo poliédrico realizado sobre ele e desigualdades adicionais obtidas em decorrência deste estudo. Finalmente, descreveremos as técnicas de decomposição desenvolvidas para diminuir o tamanho das instâncias e que tiveram impacto positivo na prática.

Em um mapa de símbolos proporcionais, eventos relacionados a localizações geográficas são representados através de símbolos, cujas áreas são proporcionais às intensidades de cada evento. Em nosso projeto, os símbolos utilizados são discos opacos e encontram-se organizados na forma de uma pilha. Quando dois ou mais discos se sobrepõem, partes deles podem ficar encobertas e pode ser difícil determinar seus tamanhos. Logo, encontrar a ordem na qual eles devem ser dispostos na pilha é fundamental para que as informações sejam interpretadas corretamente. Nesse trabalho, estudamos o problema de encontrar um empilhamento que maximize a soma dos comprimentos das bordas visíveis dos discos. A complexidade deste problema ainda está em aberto e, por isso, desenvolvemos uma heurística baseada em GRASP para resolvê-lo.

Nesta palestra, apresentaremos essa heurística, descrevendo os métodos utilizados para obter soluções de alta qualidade e as estratégias que permitem executá-los eficientemente.

Nesta palestra, introduziremos a metaheurística BRKGA, recentemente introduzida por Resende e Gonçalves (2010), incluindo detalhes de sua implementação e aplicações para problemas de planejamento de redes metropolitanas e cobertura (Steiner triple covering). Discutiremos em detalhe uma implementação paralela e genérica em C++ com OpenMP que pode ser facilmente utilizada em problemas de otimização combinatória.

Referência(s):
[1] M.G.C. Resende, R.F. Toso, J.F. Gonçalves, and R.M.A. Silva, “A biased random-key genetic algorithm for the Steiner triple covering problem.” Optimization Letters (Feb. 2011).
[2] M.G.C. Resende, R.F. Toso, D. Wang, R. Doverspike, “Design of metro Ethernet networks.” Talk given at the INFORMS Annual Meeting, Austin, TX (Nov. 2010).

Serão apresentados dois problemas de transporte marítimo baseados em casos reais. Ambos os problemas podem ser enquadrados na área do Inventory Routing, isto é, são problemas que combinam a gestão de stocks com a determinação de rotas. Considerando conjuntos de portos de origem e portos de procura dos produtos, com capacidades limitadas de stock, e uma frota de navios, o objectivo é o de determinar o plano de abastecimento de menor custo. Em ambos os problemas é considerado um horizonte temporal discreto com taxas de oferta e de procura nos portos que dependem do periodo.

Para ambos os problemas serão descritas e comparadas (teórica e computacionalmente) diferentes formulações matemáticas (em programação linear inteira mista) e serão discutidas formas de melhorar essas formulações, nomeadamente através da inclusão de desigualdades válidas.

Neste seminário vou descrever dois problemas sobre grafos que encontrei como sub-problemas em outras aplicações. Não sei se são fáceis ou difíceis, abertos ou resolvidos.

O primeiro problema é definir um conceito coerente de “grafo esparso”. Tenho um algoritmo numérico que opera sobre uma malha dada $G$. O algoritmo é muito eficiente quando $G$ é planar, e parte dessa eficiência decorre das seguintes propriedades: (1) em qualquer grafo simples planar conexo com $V$ vértices e $E$ arestas, temos $E = O(V)$; (2) certas operações de simplificação local preservam planaridade. A questão é como estender esse algoritmo para malhas em dimensões maiores. Para isso precisaríamos encontrar uma classe de grafos “esparsos” que (0) inclui malhas regulares $d$-dimensionais, (1) satisfaz $E = O(V)$ e (2) é fechada sob certas operações de simplificação local.

O segundo problema é a caracterização de grafos que são esqueletos de triangulações. Uma triangulação bidimensional pode ser vista como um desenho de um grafo em uma superfície compacta (esfera, toro, fita de Moebius, etc.) onde cada face é um triângulo. A questão é: quando é que um grafo simples tem uma triangulação? (Todo grafo pode ser desenhado em alguma superfície, mas as faces resultantes não são necessariamente triângulos.) Verifica-se que $K_6$ admite triangulação; será que $K_7$ admite? Este problema pode ser definido de maneira inteiramente combinatória (sem falar em superfície), e nessa forma ele pode ser generalizado para $d$ dimensões.

Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we wish to find the smallest $\epsilon$ such that, for $n$ sufficiently large, every $n$-vertex planar graph contains a dominating set of size at most $\epsilon n$. We prove that $1/4 \leq \epsilon \leq 1/3$, and we conjecture that $\epsilon=1/4$. For triangulated discs we obtain a tight bound of $\epsilon=1/3$. The upper bound proof yields a linear-time algorithm for finding an $(n/3)$-size dominating set.

Reference(s):
[1] L. R. Matheson e R. E. Tarjan. Dominating sets in planar graphs. European Journal of Combinatorics, 17 (3), 1996.

The Berge–Fulkerson Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, a useful technical lemma is proved that a cubic graph $G$ admits a Berge–Fulkerson coloring if and only if the graph $G$ contains a pair of edge-disjoint matchings $M_1$ and $M_2$ such that (i) $M_1 \cup M_2$ induces a 2-regular subgraph of $G$ and (ii) the suppressed graph $G \setminus M_i$ , the graph obtained from $G \setminus M_i$ by suppressing all degree-2-vertices, is 3-edge-colorable for each $i = 1,2$. This lemma is further applied in the verification of Berge-Fulkerson Conjecture for some families of non-3-edge-colorable cubic graphs (such as, Goldberg snarks, flower snarks).

Reference(s):
[1] Hao, R, Niu J, Wang X, Zhang C Q, Zhang T. A note on Berge-Fulerson coloring.. Discrete Mathematics, 309(13), 2009.

NMR experiments can provide distances between pairs of hydrogens of a protein molecule. The problem of identifying the coordinates of all atoms of a molecule by exploiting the information on the distances is a Molecular Distance Geometry Problem (MDGP). We define an artificial backbone, where a particular ordering is given to the hydrogens and also to the atoms of the protein backbone. This ordering allows to formulate the MDGP as a combinatorial optimization problem, to which we refer as the Discretizable MDGP (DMDGP) and that we efficiently solve by an exact algorithm, the Branch and Prune (BP) algorithm.

A pedigree of a population of individuals is a finite directed acyclic graph in which each vertex has in-degree 0 or 2. The sink vertices in a pedigree are living individuals and sources are the founders of the population. Can we construct pedigrees from observations on living individuals? I will give an overview of a broad range of theoretical questions in my attempts to adapt phylogenetic methods to study the above question. In particular, I would like to introduce many combinatorial questions closely related to enumeration, graph reconstruction from subgraphs, line graphs of graphs and permutation groups, and statistical identifiability and consistency questions for simple models of recombination and mutation.

Extremal combinatorics are among the popular and fast growing fields of mathematics which has strong connections to theoretical computer science. Typical questions in this area concern extremal values parameters of given objects can attain under certain restrictions, e.g., the number of edges a graph can have without containing a clique of size $k$, or the density a subset of the first $n$ numbers can attain without exhibiting an arithmetic progression of length $k$.

In this talk I shall give a (mostly nontechnical) introduction into this area with focus on the role of (pseudo-)randomnessU in the questions, the answers and the tools.

Em 1966, durante um colóquio em Teoria dos Grafos, Gallai[1] perguntou se para qualquer grafo conexo, todos os caminhos mais longos têm um vértice comum. Poucos anos depois, Walther[2] mostrou que isso não é sempre verdade, exibindo um contra-exemplo. Por outro lado, sabe-se que a resposta é positiva para árvores e algumas outras classes de grafos. Em 1990, Klavzar e Petkovsek[3], provaram que a resposta também é positiva para grafos divididos e cactos. Mais recentemente, em 2004, Balister, Gyori, Lehel e Shelp[4] estabeleceram um resultado semelhante para grafos arco-circulares. Nesse seminário, mostraremos que qualquer grafo exoplanar conexo também tem um vértice comum a todos os seus caminhos mais longos.

Outra pergunta relacionada foi levantada em 1995, no 15th British Combinatorial Conference[5]: Quaisquer três caminhos mais longos em um grafo conexo têm um vértice em comum? Mostraremos que, para grafos conexos em que todos os blocos não triviais são Hamiltonianos, existe um vértice comum a quaisquer três caminhos mais longos.

Ambos os resultados são uma generalização de um resultado anterior de Axenovich[6] que diz que para todo grafo exoplanar conexo, existe um vértice comum a quaisquer três caminhos mais longos.

Referência(s):
[1] Gallai, T., Problem 4, in: Theory of Graphs (1968), 362.
[2] Walther, H., Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen, J. Combinatorial Theory 6 (1969), 1–6.
[3] Klavzar, S. and M. Petkovsek, Graphs with non empty intersection of longest paths, Ars Combin. 29 (1990), 13–52.
[4] Balister, P., E. Györi, J. Lehel and R. Schelp, Longest paths in circular arc graphs, Combin. Probab. Comput. 13 (2004), 311–317.
[5] Research problems, Discrete Mathematics 167/168 (1997), 605–615, 15th British Combinatorial Conference.
[6] Axenovich, M., When do three longest paths have a common vertex?, Discrete Mathematics, Algorithms and Applications 1 (2009), 115–120.

It was conjectured by Fulkerson that the edge-set of any bridgeless graph can be covered by six cycles (union of circuits) such that each edge is in exactly four cycles. We prove that if Fulkerson′s conjecture is true, then the edge-set of every bridgeless graph $G$ can be covered by three cycles whose total length is at most $\frac{22}{15} |E(G)|$. We also prove that there are infinitely many bridgeless graphs $G$ whose edge-set cannot be covered by three cycles of total length less than $\frac{22}{15} |E(G)|$.

Reference(s):
[1] Fan, G., and A. Raspaud, Fulkerson’s Conjecture and circuit covers. J. Combin. Theory Ser. B 61 (1994), 133–138.

The Metric Facility Location Problem (MFLP) consists of a set of cities and a set of facilities with opening costs, such that the distance function of cities and facilities is a metric. The objective is minimize the total connection and opening cost. We describe the 1.861-approximation by Jain et al., and present the dual-fitting analysis based on the so called family of factor-revealing linear programs. We informally discuss how the factor-revealing programs may be used to elegantly obtain approximation guarantees of algorithms for this and similar problems. Also, we give some intuition on how the factor-revealing is analyzed, and how to obtain a more tight 1.816-approximation factor for the Jain’s algorithm.

Reference(s):
[1] Jain, Kamal, Mahdian, Mohammad, Markakis, Evangelos, Saberi, Amin, and Vazirani, Vijay V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM 50(6), 795–824, 2003.
[2] Mahdian, Mohammad: Facility Location and the Analysis of Algorithms through Factor-Revealing Programs, Massachusetts Institute of Technology, 2004.