Universidade Federal do Ceará
ParGO – Paralelismo, Grafos e Otimização

Seminários 2008-2015

2015

• Data/horário: 13/11/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Paulo Henrique Macedo de Araujo (aluno doutorado, MDCC, UFC)
• Título: The minimum connected dominating set problem (MCDSP)
• Resumo: A dominating set in an undirected connected graph $G=(V,E)$ is a set $D \subset V$ such that $\Gamma(D)=V$, where $\Gamma(D)= D \cup \{j \in V |\{i,j\} \in E, i \in D\}$. The minimum dominating set problem consists in finding a dominating set of minimum cardinality. A connected dominating set is a dominating set $D$ such that the subgraph $G(D)=(D,E(D))$ is connected, where $E(D)= \{\{i,j\} \in E | i \in D, j \in D\}$. The minimum connected dominating set problem (MCDSP) consists in identifying a connected dominating set of minimum cardinality. Applications that specifically involve MCDSP arise in the design of ad-hoc wireless sensor networks, where network topologies may change dynamically (Balasundaram and Butenko 2006). They could also be found in the design of defense strategies against the attack of worms in peer-to peer networks (Liang and Sencun 2007). Another application appears in Chen et al. (2010) and addresses the design of fiber optics networks where regenerators of information may be required at some network vertices (Chen et al. 2010). Regenerators, which are expensive equipments, are necessary to boost information quality, degraded after traveling long distances in cable. Finally, minimum connected dominating sets are also suggested as models to investigate protein-protein interactions (Milenkovi ´c et al. 2011). In the literature, the best know exact algorithm for the MCDSP is based on a Benders decomposition algorithm in a integer programming model (Lucena et al. 2014). We use the linear relaxation of the integer programming model in a branch-and-cut algorithm to make another exact algorithm for the MCDSP. We also develop variants of the branch-and-cut algorithm, including one that uses a combinatorial branch strategy. Computational results on a large set of randomly instances used in the literature are presented along with the comparisons of all the algorithms quoted above.

• Data/horário: 23/10/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Prof. Dr. Mamadou Kante (Université Blaise Pascal)
• Título: On output-sensitive algorithms: the case of minimal transversals and minimal dominating sets
• Resumo: A transversal in a hypergraph is a subset of its ground set that hits every of its hyperedges. It is a fifty-year open problem (Hypergraph Transversal problem) whether one can list the set of (inclusion-wise) minimal transversals of a given hypergraph in time polynomial in the cumulated sizes of the hypergraph and its set of minimal transversals (such algorithms are called output-polynomial algorithms). This is an important problem as it is equivalent to the dualisation of monotone boolean functions and several problems in data-mining are special cases of this problem (or equivalent). Recently, we proved that it is in fact (polynomially) equivalent to the same question for minimal dominating sets in graphs, that we call Dom-Enum (a dominating set is a subset of vertices that intersects the neighbourhoods of every vertex). This surprising result has the advantage of bringing tools from graph theory to deal with the  hypergraph Transversal problem. In this talk I will present our recent works on this problem and related ones.

• Data/horário: 15/10/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Malgorzata Sulkowska (Wroclaw University of Technology)
• Título: On some results in optimal stopping on partial orders and graphs
• Resumo: General formulation of an online decision problem can be stated as follows. The elements of a finite structure are being revealed one by one to a selector in some random order. At time $t$ the selector examines the t-th element and knows the structure induced by the elements that have come till time $t$. The selector’s aim is to choose the currently examined element maximizing the probability that it belongs to some earlier prescribed subset (e.g. is maximal in the whole structure). We mention a few basic results when structures under consideration are partially ordered sets and directed graphs.

• Data/horário: 09/10/2015 – 14:30h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Adilson Elias Xavier (UFRJ)
• Título: Hyperbolic Smoothing Method:
  A Novel Approach for Solving Clustering Problems
• Resumo:Clustering analysis can be done according to numerous criteria, through different mathematical formulations. The methodology considered here deals with clustering problems that have a common component: the measure of a distance, which can be done following different metrics. The methodology, called hyperbolic smoothing, has a wider scope, and can be applied to clustering according to distances measured in different metrics, such as Euclidian, Minkowski, Manhattan and Chebychev norms. By smoothing we fundamentally mean the substitution of an intrinsically non-differentiable two-level problem by a completely differentiable single-level alternative. This is achieved through the solution of a sequence of differentiable sub-problems which gradually approaches to the original problem. An additional improvement considers the partition of the set of observations into two groups: “data in the frontier” and “data in gravitational regions”. The resulting effect is a desirable substantial reduction of the computational effort necessary to solve the clustering problems.The talk will consider three clustering formulations:1 – Among many criteria, the most natural, intuitive and frequently adopted criteria is the minimum sum-of-squares clustering (MSSC);2 – The minimum sum of distances clustering problem according to the Euclidian metric, which is analogous to the multisource Fermat-Weber location problem;3 – The minimum sum of distances clustering problem according to the Manhattan metric.In order to show the distinct performance of the proposed methodologies, a set of computational results obtained by solving large test problems is presented. In particular we will present unprecedented results to large scale multisource Fermat-Weber problems, which were obtained recently.

• Data/horário: 03/09/2015 – 16:00h.
• Local: Bloco 914, sala 1.
• Palestrante: Prof. Dr. Leandro Pimentel (UFRJ)
• Título: Percolação Maximal e Campos de Busemann
• Resumo: Em modelos de percolação maximal na grade quadrada estuda-se propriedades geométricas de caminhos que maximizam o tempo aleatório de percolação entre dois pontos. Neste seminário veremos como a construção de campos de Busemann em tais modelos pode nos ajudar a responder algumas questões fundamentais.

• Data/horário: 28/08/2015 – 16:00h.
• Local: Bloco 952, sala 2.
• Palestrante: Marcio Costa Santos (Doutorando, UTC)
• Título: Como um pessismista desconfiado trabalha em otimização (ou uma rapida introdução a otimização robusta)
• Resumo:Devido a erros humanos/numéricos ou pela própria natureza do problema, as vezes não podemos confiar nos dados que nos são apresentados, mas, ainda assim, precisamos de uma solução “ótima” para o problema. Nesse seminário apresentamos, de maneira sucinta, os principais conceitos e métodos associados a otimização com incerteza do ponto de vista de otimização robusta. Otimização robusta é um paradigma de otimização sobre incerteza relativamente novo, que se destaca por não usar ferramental estatístico avançado como programação estocástica e se basear principalmente em características combinatórias dos problemas.

• Data/horário: 07/08/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Nicolas Almeida Martins (doutorando, MDCC, UFC)
• Título: Combatendo a espionagem em um grafo
• Resumo: Jogos de perseguição tem sido estudados desde 1732 quando Pierre Bouguer estudou o problema de um navio pirata perseguindo um navio mercante. Em grafos, o problema de perseguição mais famoso é o jogo de polícia e ladrão, introduzido  independentemente por Nowakowski e Win-kler e Quilliot, e desde sua criação diversas variações do jogo foram propostas. Neste trabalho introduzimos um novo jogo de perseguição em grafos: O jogo de espiões. Dado um grafo $G$ e dois inteiros $s$ e $d$, um jogador $R$ controla um espião e um jogador $C$ controla um conjunto de guardas. Inicialmente $C$ posiciona seus guardas nos vértices de $G$ e posteriormente $R$ posiciona seu espião. A partir de então $C$ e $R$ movem seus peões alternadamente de acordo com a velocidade dos mesmos(os policiais tem velocidade 1 e o espião tem velocidade $s$). Se ao final do turno do jogador $C$ o espião estiver a uma distância superior a $d$ de todos os vértices ocupados por guardas, ele se comunica com seu país e conta os segredos que descobriu. O jogador $R$ vence o jogo se consegue se comunicar infinitas vezes durante o curso da partida, caso contrário a vitória é do jogador $C$. Ao contrário de outros jogos de perseguição o jogador $C$ não tem o objetivo de capturar o espião e o jogo possui infinitos turnos. Mostramos que quando $s=3$ o jogo de espiões é NP-difícil mesmo para grafos com diâmetro 5. Além disso a versão do jogo em Digrafos é NP-difícil em DAG’s. Por último mostramos que a versão do jogo em que o jogador $R$ escolhe a posição de seu espião antes do jogador $C$ posicionar seus guardas é PSPACE-difícil.

• Data/horário: 19/06/2015 – 16:00h.
• Local: Bloco 952, sala de seminários do Dept. Computação.
• Palestrante: Thiago Marcilon (doutorando, MDCC, UFC)
• Título: Tempo de Infecção de Grafos
• Slides
• Resumo:Dado um grafo com alguns vértices inicialmente doentes, um vértice sadio é infectado se for vizinho de dois vértices doentes.
  Vértices doentes nunca são curados (como nos filmes de zumbi). Um problema muito estudado é a computação do número mínimo de vértices para infectar o grafo inteiro. Outro problema muito estudado recentemente é o tempo máximo para infectar o grafo inteiro. Ou seja, sabendo que o grafo inteiro será infectado (todos vão virar zumbis), qual o tempo máximo para isso ocorrer? Vários artigos recentes obtiveram algoritmos polinomiais para esse problema em grafos gride retangulares, grafos cordais ou cografos. No WG-2014, provamos que é NP-Difícil determinar se um grafo pode ser infectado em tempo $4$ e obtivemos um algoritmo polinomial para tempo $3$. Neste seminário, apresentaremos alguns desses resultados e principalmente os publicados agora no WG-2015: o tempo máximo de infecção é NP-Difícil em subgrafos de grides e é polinomial em grides sólidos com grau máximo $3$. O problema em grides sólidos com grau máximo $4$ permanece em aberto, entre outros. Vários autores desses artigos são professores do ParGO, como Fabricio Benevides, Victor Campos, Rudini Sampaio e Ana Shirley Silva.

• Data/horário: 30/04/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Antônio Josefran (doutorando, IME-USP)
• Título: Conteiners de Hipergrafos
• Resumo:Em 2013, Saxton e Thomason, e Balogh, Morris e Samotij desenvolveram independentemente uma técnica conhecida como contêineres de hipergrafos. Esta técnica vem sendo utilizada na obtenção de vários resultados para problemas de imersão. Por exemplo, Morris e Saxton, em 2013, utilizaram esta técnica para provar que o número de grafos livres de $C_{2k}$, onde $k$ é um inteiro positivo, é no máximo $2^{O(n^{1 + 1/k})}$. Neste seminário, irei apresentar uma introdução a esta nova técnica com muitos exemplos didáticos e aplicações.

• Data/horário: 12/02/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Prof. Dr. Ago Riet (Universidade de Tartu, Estônia)
• Título: Permutation Codes
• Resumo: Permutation codes have a potential use for error detection and correction in flash memories. All permutations of numbers $1,2,…,n$ form a group under composition, called the symmetric group $Sn$. There are several commonly used distance metrics between elements in $Sn$, so this set is viewed as a metric space. A code of minimum distance $d$ is simply a subset of $Sn$ in which all pairwise distances are at least $d$ in one of our distance metrics. Constructing large codes is one of the main problems in coding theory. I will talk about the combinatorics of permutation codes, ways to obtain lower and upper bounds on maximum code size and codes attaining these bounds.

• Data/horário: 30/01/2015 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Prof. Dr. Ignasi Sau
• Título: FPT algorithm for a cut problem and some applications
• Resumo: In this talk we will sketch the main idas of a Fixed-Parameter Tractable (FPT) algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the “edge contraction” technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation:(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism.(2) An FPT algorithm for a graph partitioning problem, called Min-Max Graph Partitioning.(3) An FPT 2-approximation algorithm for computing the “tree-cut width” of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.If time permits, we will partially discuss the above applications of our main algorithm. No previous knowledge of Paramerized Complexity will be assumed in the talk. This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.

2014

• Data/horário: 07/11/2014 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Prof. Rudini Sampaio (DC)
• Título: Fixed Parameter Tractability e Aplicações de Lógica em Algoritmos
• Slides
• Resumo: Neste seminário, vamos mostrar como usar alguns resultados clássicos de lógica (como o Teorema de Courcelle e o Teorema de Frick-Grohe) para obter resultados na área de grafos e algoritmos. Mostraremos ainda relações com Fixed Parameter Tractability e a Hierarquia W.

• Data/horário: 05/10/2014 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante:Antonio Josefran de Oliveira Bastos
• Título: Álgebra de Flag e o Problema do Empacotamento em Permutações
• Resumo: Em 2007, Alexander Razborov apresentou a teoria de Álgebra de Flag como uma nova abordagem para a obtenção de resultados assintóticos.
  Essa teoria mostrou-se muito flexível e poderosa, de tal forma que foi amplamente utilizada na obtenção de vários resultados para diversas estruturas combinatóricas, tais como permutações, grafos, hipergrafos, etc.
  Neste trabalho, estudamos a teoria de Álgebra de Flag com a finalidade de utilizá-la na abordagem de alguns problemas assintóticos de permutações.

• Data/horário: 01/08/2014 (sexta 14h)
• Palestrante:Prof. Victor Campos (DC-UFC)
• Título: On Connected Identifying Codes
• Resumo: An identifying code in a graph $G$ is a set $C$ of vertices of $G$ such that the closed neighbourhood of every vertex contains a unique and non-empty subset of $C$. We say that $C$ is a connected identifying code if $G[C]$ is connected. We prove that if a finite graph $G$ on $n$ vertices has maximum degree D, then any connected identifying code $C$ satisfies $|C|\geq (2n-2)/(D+1)$. We also show that this bound is best possible and that the coefficient of $n$ cannot be improved for D-regular graphs. We also show that the minimum density of connected identifying codes for the infinite triangular, hexagonal and square lattices are 1/3, 1/2 and 2/5, respectively.

• Data/horário: 05/08/2014 (terça 16h)
• Palestrante: Bruno Petrato Bruck (convidado externo)
• Título: Non-Elementary Formulations for the Single Vehicle Routing Problem with Deliveries and Selective Pickups
• Resumo: In the single vehicle routing problem with deliveries and selective pickups a vehicle departs from a depot to perform a tour through a given set of customers, each requiring either a delivery, a pickup, or both (combined demand). While all deliveries must be performed, the pickups are optional and generate a revenue if performed. In case of a combined demand the vehicle is allowed to visit either once or twice such customer. The objective is to minimize the total cost, which is given by the total transportation cost minus the revenue generated by the performed pickups. The problem is important because models several real-world applications, including beverage and electronic components distributions, courier service transportation, and reverse logistics. All exact algorithms in the literature solve the problem by looking for Elementary tours on an extended network, which is obtained by splitting each combined demand customer into two different customers, one requiring only the delivery and the other only the pickup. Because this can result in a significant loss in performance, in this work we focus instead on the original problem network and present formulations that can yield non-Elementary tours. Through the use of Benders Decomposition, several families of valid inequalities, and tailored optimization techniques based on Branch\&Cut frameworks, we are able to outmatch previous results in the literature and obtain the optimal solution for all the available benchmark instances. In addition, we generalize the algorithms to several problem variants, including the case of split-deliveries, temporary dropoffs, and mandatory pickups.

• Data/horário: 14/08/2014 (quinta 16h)
• Palestrante: TATIANE FERNANDES FIGUEIREDO (defesa de mestrado)
• Título: Problema de Formação de Equipes Sociotécnicas: Complexidade, Formulações Matemáticas e Resultados Computacionais
• Resumo: Um dos principais mecanismos organizacionais para a melhoria da competitividade no mercado atual é a adequação da estrutura da organização à sua missão. Uma das alternativas de adaptação estrutural é a formação de equipes de trabalho cooperativo que vem se tornando uma das peças centrais para a flexibilização do processo produtivo. Equipes harmoniosas e competentes trabalham de forma mais dinâmica, sobressaindo-se em requisitos como facilidade de comunicação, integração de esforços e troca de conhecimentos. Porém, diversos fatores podem alterar o desempenho destas equipes: distribuição adequada de tarefas, fatores psicológicos, físicos, de convívio, dentre outros. Enquanto fatores psicológicos e físicos são dificilmente previsíveis, fatores como o convívio e distribuição de tarefas podem ser avaliados através de metodologias criadas por pesquisadores da área de gestão de pessoas. Utilizando os conceitos da Teoria dos Sistemas Sociotécnicos, este trabalho define matematicamente os problemas de formação de equipes cooperativas considerando separadamente restrições sociais e técnicas, apresentando a complexidade computacional dos mesmos. Posteriormente é apresentado o problema principal, foco deste trabalho, que considera conjuntamente requisitos sociais e técnicos para criação de equipes de trabalho cooperativo, denominado FEST (Problema de Formação de Equipes Sociotécnicas). A partir da análise do sistema sociotécnico da organização, este trabalho propõe duas formulações matemáticas e uma meta-heurística para o FEST. Apresentamos as provas de corretude de ambas as formulações e um algoritmo polinomial para separar as restrições da segunda formulação. Propomos também desigualdades válidas para fortalecer ambas as formulações e mostramos que algumas delas induzem facetas. Por fim, analisamos estatisticamente o desempenho das formulações e da meta-heurística apresentadas.

• Data/horário: 22/08/2014 (sexta 16h)
• Palestrante:Prof. Fabrício Benevides (MAT-UFC)
• Título: EDGE-COLORINGS OF GRAPHS AVOIDING COMPLETE GRAPHS WITH A PRESCRIBED COLORING
• Resumo: For any fi xed graph $F$, we say that a graph $G$ is $F$-free if it does not contain $F$ as a subgraph. We denote by $ex(n,F)$ the maximum number of edges in a $n$-vertex graph which is $F$-free, known as the Turán number of $F$.
  In 1974, Erdos and Rothschild considered a related question where we count the number of certain colorings. Given an integer $r$, by an $r$-coloring of a graph $G$ we mean any $r$-edge-coloring of $G$. In particular, it does not have to be proper and does not have to use all $r$ colors. Let $c_{r,F}(G)$ be the number of $r$-colorings of $G$ such that every color class is $F$-free. They considered the problem of fi nding $c_{r,F}(n) = \max c_{r,F}(G) where the maximum is over all $n$-vertex graphs $G$. Let us say that $G$ is extremal for $c_{r,F}(n) if it realizes the above maximum. Clearly, $c_{r,F}(n)\geq r^{ex(n,F)$, as we take $G$ to be the Turán graph and color it arbitrarily. The problem of determining $c_{r,F}(n)$ was investigates by several authors, for various classes of graphs such as: complete graphs, odd cycles, matchings, paths, stars and for hypergraphs. One common concern is to determine when the Turán Graph is extremal for $c_{r,F}(n)$ (with $r$ fi xed and $n$ large). Here we consider a natural generalization of the above. Given an $r$-colored $k$-vertex graph $F’$, we consider the number of $r$-edge-colorings of a larger graph $G$ that avoids the pattern of $F’$. More formally, $c_{r,F’}(G)$ denote the number or $r$-colorings of $G$ such there are no $k$ vertices of $G$ that induce a colored graph isomorphic to $F’$. For example, the above problem consists of the case where $F’$ is a colouring of $F$ that uses only one of the $r$ colors. We note that Balogh has also considered a related but not analogous colored version of the problem. He considered the number $C_{r,F’}(G)$ of colorings of $G$ which do not have a set of $k$-vertices colored exactly as in $F’$. In this case, if $F’$ has only one color, $C_{r,F’}(G)$ is the number of colorings of $G$ which does not contains $F’$ in this particular color. So $c_{r,F’}(G)\leq C_{r,F’}(G)$. Balogh proved that in the case where $r=2$ and $F’$ is a 2-coloring of a clique that uses both colors then $C_{2,F’}(n)= 2ex(n,F’)$ for $n$ large enough. Here, we focus on the case where $r=3$. Let $F’_3$ be a 3-colored $K_3$. We proved that, if the three colors are used in $F’_3$, then the complete graph on $n$ vertices is the extremal graph for $c_{3,F’_3}(n)$. If only two colors are used in $F’_3$, then the Turán graph is extremal for $c_{3,F’_3}(n)$ (while this is trivialy not true for $C_{3,F’_3}(n)$. Generalizing the previous statement, when $r=3$ and $F’_k$ is a coloring of $K_k$ that uses only two colors one of which induces a graph $H$ whose Ramsey Number is smaller than $k$, then the Turán graph is extremal for $c_{3,F’_k}(n)$.

• Data/horário: 31/07/2014 – 15:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Dr. Fabio Carlos Sousa Dias
• Título: Problemas de Árvore Geradora Mínima com Restrições de Grau: complexidade, formulações e algoritmos
• Resumo: O Problema de Árvore Geradora Mínima com Restrição de Grau Mínimo (Min-Degree Constrained Minimum Spannig Tree – MD-MST) consiste em encontrar uma árvore geradora mínima de um grafo onde cada vértice ou é folha da árvore ou satisfaz uma restrição de grau mínimo. Os vértices folhas são chamados terminais e os demais são os centrais. Definimos e estudamos uma variação do desse problema, que denotamos MDF-MST, onde os terminais e centrais são definidos a priori. Mostramos que o problema é NP-Difícil e está em FPT, parametrizado pelo número de centrais. Identificamos também casos onde o problema torna-se polinomial. Propomos várias formulações de programação inteira para o problema e comparamos computacionalmente a qualidade do limite inferior gerado por suas relaxações lineares. Propomos e testamos uma relaxação lagrangeana para o problema, que usamos também para definir heurísticas lagrangenas. Definimos heurísticas gulosas, uma bisca VND e uma heurística VNS. Apresentamos uma decomposição de Benders. Propomos uma nova heurística geral que combina ingredientes da Decomposição de Benders com Método de Subgradientes, a qual denominamos Heurística de Subgradientes. Aplicamos tal heurística ao MDF-MST. Todos esses algoritmos foram implementados, testados e comparados com o solver CPLEX. A eficiência computacional dos algoritmos propostos,  specialmente a Relaxação Lagrangeana, é comparável com a do CPLEX, e superior em vários casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este último onde a restrição sobre os centrais é de grau máximo).
  Quando comparamos os resultados computacionais com a literatura, podemos concluir que os algoritmos são competitivos.

• Data/horário: 30/05/2014 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Prof. Dr. Javier Marenco (Universidad Nacional de General Sarmiento, Argentina)
• Título: Solving waste collection problems with integer programming
• Resumo: The logistics of waste collection give rise to challenging problems for the combinatorial optimization community. The basic models correspond to particular instances of the traveling salesman problem and the chinese postman problem in mixed graphs. Although these problems are quite well solved in practice by integer programming techniques, applications of waste collection usually include additional features that may greatly complicate their computational resolution. In this talk, I will give an overview of such models based on our experience in Argentina, and will point to difficult combinatorial optimization problems arising in this context.

• Data/horário: 23/05/2014 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Thiago Marcilon (Doutorando, MDCC, UFC)
• Título: The maximum time of 2-neighbour bootstrap percolation: complexity results
• Slides
• Resumo: In $2$-neighbourhood bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least $2$ already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved that deciding if $t(G)\geq k$ is polynomial time solvable for $k=2$, but is NP-Complete for $k=4$ and is NP-Complete if the graph is bipartite and $k=7$ (Eurocomb-2013). In this paper, we solve the open questions. We obtain an $\Theta(m n^5)$-time algorithm to decide if $t(G)\geq 3$ in general graphs. In bipartite graphs, we obtain an $\Theta(m n^3)$-time algorithm to decide if $t(G)\geq 3$ and an $\Theta(m n^{13})$-time algorithm to decide if $t(G)\geq 4$. We also prove that deciding if $t(G)\geq 5$ is NP-Complete in bipartite graphs.

• Data/horário: 16/05/2014 – 16:00h.
• Local: Bloco 914, sala 3.
• Palestrante: Prof. Dr. Rudini Menezes Sampaio (Departamento de Computação, UFC)
• Título: Inaproximabilidade de parâmetros da Convexidade P3 e da Convexidade Geodésica em grafos
• Slides
• Resumo: Nessa palestra, nós apresentamos vários resultados novos de inaproximabilidade de parâmetros da Convexidade P3 e da Convexidade Geodésica em grafos. Nós provamos que determinar o número de fecho (hull number) é APX-difícil, determinar o número de Carathéodory, de Radon e de convexidade é $O(n^{1-\epsilon})$-inaproximável em tempo polinomial para qualquer $\epsilon>0$, a menos que P=NP, e provamos que o número de intervalo é W[2]-difícil e é $O(\log n)$-inaproximável em tempo polinomial, a menos que P=NP. Provamos ainda que número de fecho (hull number) é NP-Dificil mesmo em subgrafos de grides. Alguns desses resultados foram apresentados no WAOA-2013 e no LAGOS-2013. São trabalhos em conjunto com Érika Coelho (UFG), Rafael Teixeira (UFC), Mitre Dourado (UFRJ), Jayme Szwarcfiter (UFRJ) e Vinicius Santos (UERJ). Temos ainda vários problemas em aberto para os estudantes interessados em fazer pesquisa.

• Data/horário: 09/05/2014 – 16:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Profa. Dra. Ana Shirley Silva (Departamento de Matemática, UFC)
• Título: Coloração Conexa Gulosa de Grafos
• Resumo: Uma ordem conexa dos vértices de um grafo G é uma ordem $v_1 < v_2 <\ldots < v_n$ de $V(G)$ tal que cada $v_i$ tem pelo menos um vizinho em $v_1,\ldots,v_{i-1}$, para todo $i \in \{2,…,n\}$. Uma coloração gulosa conexa é uma coloração obtida aplicando o algoritmo guloso de coloração a uma ordem conexa de $V(G)$. Neste trabalho, estudamos o parâmetro $\Gamma_c(G)$, o número máximo $k$ para o qual $G$ admite uma coloração gulosa conexa com $k$ cores, e $\chi_c(G)$, que o mínimo correspondente. Nós mostramos que calcular $\Gamma_c(G)$ é NP-difícil mesmo que $G$ seja um grafo cordal ou o complemento de bipartite. Além disso, mostramos que se G é bipartite, então $\Gamma_c(G) = 2$. A respeito do parâmetro $\chi_c(G)$, primeiro mostramos que, para todo $k>3$, existe um grafo G $k$-cromático com $\chi_c(G) > \chi(G)$. Em seguida, mostramos que, para todo grafo $G$, $\chi_c(G) \leq \chi(G) + 1$, e que decidir se $\chi_c(G)$ é $\chi(G)$ ou $\chi(G)+1$ é NP-completo.

• Data/horário: 20/02/2014 – 14:00h.
• Local: Bloco 952, sala de seminários.
• Palestrante: Paulo Henrique Macedo de Araujo (doutorando, MDCC, UFC)
• Título: Uma Heurística Lagrangeana com Paralelismo para o Problema de Ponderação de Rodadas
• Resumo: Aplicações relevantes de problemas de coloração aparecem de diversas formas na área de telecomunicações. No âmbito das redes sem fio, nas quais as comunicações são realizadas via ondas de rádio, uma aplicação que se destaca diz respeito a comunicações ponderadas por demandas relativas nos nós, chamada de problema de Ponderação de Rodadas (PR). Para essa aplicação, a rede de comunicação é modelada por um grafo, chamado de grafo da rede, em que os vértices representam os nós da rede (elementos que podem enviar ou receber mensagens) e as arestas as possíveis comunicações entre nós. Uma transmissão é o envio de uma mensagem de tamanho unitário por um nó da rede através de um canal até outro nó. O tempo consumido por uma transmissão é constante e igual a uma unidade de tempo. Uma hipótese feita é que os tempos de atraso referentes aos processamentos realizados na saída e na chegada da mensagem são desconsiderados. Nessa rede, há nós identificados como nós de origem e nós de destino. Nós de origem são nós que possuem demanda de mensagens para enviar através da rede, enquanto que nós de destino são nós que processam localmente uma mensagem recebida. Além disso, cada nó da rede dispõe de uma memória de retenção de dados para armazenar mensagens em trânsito. Uma limitação à eficiência da rede é devido a dois fatores: o alcance finito de transmissões (como resultado da potência de emissão das antenas) e interferências causadas por transmissões simultâneas (devido ao fato de as transmissões serem realizadas em uma mesma frequência).Uma rodada é um conjunto de transmissões simultâneas sem interferência, enquanto um protocolo é uma coleção de rodadas. Um escalonamento é uma ordenação de um protocolo. A execução de um escalonamento consiste em efetuar simultaneamente as transmissões de cada rodada, tomando a sequência estabelecida. O tamanho do período de um escalonamento se refere ao tempo de duração de uma execução do mesmo. Dado um escalonamento executado repetidamente, a vazão de um nó de origem é a razão da quantidade de mensagens enviadas por ele durante uma única execução do escalonamento sobre o tamanho do período. A vazão total é soma das vazões dos nós de origem. Uma solução para o problema PR é um escalonamento que satisfaz a demanda de mensagens para cada nó de origem. O objetivo é determinar uma solução que maximize a vazão total.Nesta pesquisa, desenvolvemos e implementamos uma heurística lagrangeana para o problema PR, assim como para o problema de Coloração Fracionária, que foi estudado inicialmente para facilitar a escolha de uma estratégia de resolução do problema PR. Uma análise dos resultados computacionais através de comparações com outras heurísticas também foi feita para mostrar a qualidade da heurística desenvolvida.

2013

• Data/horário: 25/01/2013 – 16:00h.
• Local: Bloco 915, sala 1035
• Palestrante: Leonardo Sampaio
• Título: Aspectos algorítmicos do número de Grundy
• Resumo:O algoritmo guloso de coloração recebe como entrada um grafo e uma ordenação de seus vértices. Em cada iteração um vértice é colorido, segundo a ordem, com a menor cor que ainda não foi atribuída a um de seus vizinhos já coloridos. Dentre todas as ordenações possíveis dos vértices de um grafo, o maior número de cores utilizados pelo algorítmo guloso é o número de Grundy do grafo em questão. Dessa maneira, o número de Grundy de um grafo pode ser visto como o pior caso de uma aplicação do algoritmo guloso ao mesmo.Desde 1939, quando este parâmetro foi introduzido (no contexto de grafos orientados correspondentes a jogos) diversos artigos consideram o número de Grundy. A NP-completude do problema de determinar o número de Grundy de um grafo foi mostrada apenas em 1997. A complexidade do problema em classes de grafos importantes, como grafos bipartite e cordais era desconhecida. Uma de nossas contribuições foi determinar a complexidade do problema nestas classes.A teoria da complexidade parametrizada pode ser considerada como um refinamento da teoria clássica de complexidade, permitindo analisar que parâmetros relacionados à entrada de um problema tornam o mesmo difícil de resolver. A complexidade parametrizada de problemas relacionados ao cálculo do número de Grundy foi considerada neste trabalho, tendo a complexidade de alguns destes problemas sido determinada.

• Data/horário: 18/01/2013 – 16:00h.
• Local: Bloco 915, sala 1035
• Palestrante: Philippe Michelon (Université d’Avignon et des Pays de Vaucluse)
• Título: Lagrangean Relaxations and its use in Integer Programming.
• Resumo: In this talk, we will show how Lagrangean Relaxation can be used for two very classical combinatorial Optimization: the Uncapacitated Facility Location Problem and the Generalized Assignment Problem. Obviously, Lagrangean Relaxation approaches have been used since many years for computing lower bounds to minimization problems but many of its marginal benefits have not been exploited yet. Our purpose is therefore to take advantage of some of them.We present a cooperative primal-dual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a known and effective tabu search, and a dual process,which performs a lagrangean branch-and-bound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branch-and-bound nodes: decision-variable bound tightening rules applied at each node. We also propose a simple and very effective algorithm for solving the generalized assignment problem exactly. Our contribution is twofold: we re-formulate the optimization problem into a sequence of decision problems, and we solve these effectively using variable-fixing rules. The decision problems are solved by a simple depth-first lagrangean branch-and-bound method, improved by the variable-fixing rules which help prune the search tree. These rules rely on lagrangian relative costs which we compute using an existing but little-known dynamic programming algorithm.

2012

• Data/horário: 28/11/2012 – 16:00h.
• Local: Bloco 910, auditório
• Palestrante: Neal Bushaw
• Título: Turán numbers of Linear and Equibipartite Forests
• Resumo: The Turán number of a graph $H$, $ex(n,H)$, is the maximum number of edges in any graph on $n$ vertices which does not contain $H$ as a subgraph. Let $P_l$ denote a path on $l$ vertices, and $k*P_l$ denote $k$ vertex disjoint copies of $P_l$. We first determine $ex(n,k*P_3)$, answering in the positive a conjecture of Gorgol. Further, we determine $ex(n,k*P_l)$ for arbitrary $l$, and $n$ appropriately large relative to $k$ and $l$. We provide a some background on the famous Erdös-Sós conjecture, and conditional on its truth we determine $ex(n,H)$ when $H$ is a forest consisting of equibipartite trees, for appropriately large $n$. Time permitting, we will also discuss extensions to the hypergraph context. This is joint work with Nathan Kettle at the University of Cambridge.

• Data/horário: 09/11/2012 – 16:00h.
• Local: Bloco 915, sala 1035.
• Palestrante: Carlos Vinicius Gomes Costa Lima
• Título: $b$-Coloração de grafos com cintura pelo menos 5.
• Resumo:O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teórica e prática. Dado que o problema de colorir os vértices de um grafo $G$ qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo $G$, a heurística $b$ de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria $c$, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma obtemos uma coloração $c’$ com uma cor a menos que $c$. Irving e Molove definiram a $b$-coloração de um grafo $G$ como uma coloração onde toda classe de cor possui um vértice  que é adjacente as demais classes de cor. Esses vértices são chamados $b$-vértices. Irving e Molove também definiram o número $b$-cromático, denotado por $\chi_b(G)$, como o maior inteiro $k$ tal que $G$ admite uma $b$-coloração por $k$ cores. Eles mostraram que encontrar $\chi_b(G)$ de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Kratochvíl et al. mostraram que econtrar o número $b$-cromático é NP-difícil mesmo restrito a grafos bipartidos conexos. Irving e Molove também definiram o $m$-grau de um grafo, que é o maior inteiro $m(G)$ tal que existem $m(G)$ vértices com grau pelo menos $m(G)-1$. Irving e Molove mostraram que o $m$-grau é um limite superior para número $b$-cromático e mostraram que o $\chi_b(T) \in {m(T), m(T)-1}$ para toda árvore $T$. Verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número $b$-cromático de um grafo $G$. Mais especificamente, tentamos encontrar o menor inteiro $g*$ tal que, se a cintura de $G$ é pelo menos $g*$, então $\chi_b(G) \in {m(G), m(G)-1}$. Mostrar que o valor de $g*=6$ poderia ser um passo importante para demonstrar a famosa Conjectura de Erdos-Faber-Lovasz. O melhor valor conhecido para $g*$ é 9, dado por Campos et al. Conseguimos encontrar alguns resultados parciais no sentido de diminuir o valor $g*$ de 9 para 7.

• Data/horário: 14/09/2012 – 16:00h.
• Local: Bloco 915, sala 1035.
• Palestrante: Rennan Ferreira Dantas (aluno de mestrado, MDCC, UFC)
• Título: Coloração não-repetitiva e coloração clique de grafos com poucos P4s
• Slides
• Resumo:Nesse seminário, nós apresentaremos os problemas da coloração não-repetitiva e da coloração clique, que são NP-Difíceis. Nós obtemos algoritmos lineares para determinar o número cromático de Thue e o número clique-cromático de grafos $P_4$-tidy e grafos $(q,q-4)$, para q fixo. Nós também provamos que todo grafo P4-laden e todo grafo $(q,q-4)$ conexo com pelo menos q vértices é 2-clique-colorível e que toda coloração acíclica de um cografo é também não repetitiva, generalizando um resultado de Lyons em 2011. Finalmente, nós mostramos que um algoritmo de $M$. Rao em 2008 pode também ser usado para computar o número cromático acíclico de grafos distância hereditária e grafos com uma dada árvore de decomposição split com largura limitada.

• Data/horário: 01/06/2012 – 16:00h.
• Local: Bloco 915, sala 1035.
• Palestrante: Cristiana Gomes Huiban
• Título: Problema de Recoloração Convexa com 2 cores
• Resumo: Uma coloração $C$ de um grafo $G$ é uma função que atribui para cada vértice de G uma cor em $\{c_1, c_2, …, c_p\}$. Uma coloração é considerada CONVEXA, se para cada cor $c$ em $\{c_1, c_2, …, c_p\}$, o conjunto de vértices de cor $c$ induz uma componente conexa. O Problema de Recoloração Convexa com 2 cores (CRP2c) pode ser definido da seguinte forma: Dado um grafo $G$ e uma coloração $C: V(G) \rightarrow \{c_1,c_2\}$, qual é o menor número de recolorações de vértices necessárias para se obter uma coloração convexa? Nós (Manoel Campelo, Cristiana Huiban, Rudini Sampaio e Yoshiko Wakabayashi) provamos que o CRP2c é NP-difícil mesmo em grades, e que não pode ser aproximado com um fator inferior a $(1 – \varepsilon)*\ln(|V|/2 – 1)$ (com $\varepsilon>0$) mesmo em grafos bipartidos. Provamos, também, que o CRP2c pode ser resolvido em tempo polinomial para cografos, P_4-esparso e $(q,q-4)$-grafos (para $q$ fixo).

• Data/horário: 18/05/2012 – 16:00h.
• Local: Bloco 915, sala 1035.
• Palestrante: Pablo Mayckon
• Título: Subsequência Contígua de Soma Máxima com Inserção
• Resumo:Dada uma sequência possivelmente vazia $A$ de números, a “soma” de $A$ é a soma dos seus elementos, valendo zero se $A$ é vazia, e o “valor” de $A$ é a maior soma de uma subsequência contígua de $A$, incluindo-se a subsequência vazia; finalmente, uma subsequência $S$ de $A$ cuja soma é igual ao valor de $A$ é dita ser de/ter “soma máxima”. Na prática, subsequências de soma máxima modelam vários objetos de interesse, de estruturas biológicas à ocupação de memória num nó de uma rede de computadores, dentre outros. Dada uma sequência $A$ de $n$ números, o problema de se encontrar uma subsequência de soma máxima de $A$ é resolvido em tempo $\Teta(n)$ e espaço $\Teta(1)$ por um algoritmo simples desenvolvido por Joseph B. Kadane no final da década de 1970.No presente trabalho, realizado em conjunto com Ricardo Corrêa e Críston Souza, nós definimos e apresentamos resultados sobre dois problemas relacionados ao Problema da Subsequência Máxima acima mencionado. O primeiro é o de, dadas uma sequência $A$ de números e um número $x$, escolher uma posição de inserção de $x$ em $A$ que minimize o valor da sequência resultante dessa inserção. Para esse problema nós desenvolvemos um algoritmo linear, que também se aplica ao caso de subsequências circulares de $A$. O segundo problema é o de, dada uma sequência $A$ de $n$ números, encontrar uma permutação $A’$ de $A$ de valor mínimo. Para esse problema nós apresentamos uma demonstração de NP-dificuldade e um algoritmo 2-aproximativo $O(n.\log n)$.

• Data/horário: 30/03/2012 – 16:00h.
• Local: Bloco 915, sala 1035.
• Palestrante: Arthur Rodrigues Araruna
• Título: Problema do Caminho Mínimo com Restrição Probabilística de Atraso Mínimo
• Resumo:Soluções do problema de caminho mínimo são largamente utilizadas por empresas transportadoras para decidir as rotas de entrega dos produtos transportados. Entretanto, o aumento da frota de veículos e principalmente as condições das vias pelas quais trafegam tem aumentado bastante o tempo de deslocamento por entre essas rotas de forma irregular e incerta. Devido a essa variabilidade nos tempos de atraso, transportadoras que trabalham com prazos rígidos de entrega, sendo suscetíveis a multas, ou que transportam produtos perecíveis acabam por acumular grandes prejuízos.Como esse novo problema tem se tornado frequente, e por sua importância prática, desenvolvemos uma nova abordagem mais precisa que leva em conta o possível risco de descumprimento de um prazo máximo, dentro de uma margem de confiança, na seleção da melhor rota disponível. Apresentamos, juntamente ao novo problema, um esquema de decomposição em $L$ (no modelo mestre-escravo de Benders) para a resolução do problema, bem como um framework Branch-and-Bound no qual inserimos a decomposição.

• Data/horário: 16/03/2012 – 16:00h.
• Local: A confirmar.
• Palestrante: Prof. Dr. Victor Campos
• Título: Tempo máximo para Convexidade P3
• Resumo: Dado um grafo $G$ e um subconjunto $S$ de vértices inicialmente infectados com uma doença terrível, dizemos que um vértice sadio é infectado se tem dois ou mais vizinhos infectados. Sabemos que o grafo inteiro perecerá diante de tamanha catástrofe. A família do grafo deseja saber quanto tempo de vida ele ainda tem. Como médicos caridosos, desejamos dar uma resposta correta, mas o mais otimista possível para amenizar o sofrimento da família. Então queremos responder o seguinte: entre todas as infecções iniciais, qual o maior tempo de vida do grafo? Conseguimos responder isso em tempo linear quando o grafo é uma árvore. Infelizmente, para a família do grafo, esta resposta é NP-Difícil mesmo para tempo fixo maior ou igual a 4. É NP-Difícil também para grafos planares. Esse é um trabalho conjunto com Fabrício Benevides, Rudini Sampaio e Ana Silva.

2011

• Data/horário: 29/04/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Rodrigo Cavalcanti (GTEL, UFC)
• Título: Oportunidades de Pesquisa em Telecomunicações Sem Fio de Próxima Geração
• Slides
• Resumo:Sistemas de telecomunicações sem fio, notadamente os de telefonia móvel celular, representam o segmento de maior crescimento na indústria de telecomunicações. Atualmente, estes sistemas estão evoluindo para um paradigma baseado em protocolo IP, e lançando mão de técnicas sofisticadas de otimização tanto para a camada física como nas redes de acesso por ondas de rádio, de modo a realizarem alta capacidade de usuários, alta vazão de dados e qualidade de serviço satisfatória. Modernamente, as operadoras de telefonia móvel têm em foco o provimento de serviço de acesso à internet em alta velocidade como uma fonte de receita adicional. Os principais desafios neste contexto incluem o espectro limitado, a presença de interferência nas áreas urbanas mais densas e o custo da infra-estrutura. Nesta palestra apresentaremos um breve histórico da atuação do GTEL- Grupo de Pesquisa em Telecomunicações Sem Fio, da UFC, no tema, bem como a formulação de alguns problemas específicos, de relevância atual, no qual se acredita que o emprego de ferramentas matemáticas e computacionais avançadas possam contribuir para a sua solução.

• Data/horário: 15/04/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Frédéric Havet (INRIA, France)
• Título: L(p,q)-labelling and backbone colouring of graphs
• Slides
• Resumo: An $L(p,q)$-labelling of a graph $G$ is a positive integer assignment~$f$ to the vertex set~$V(G)$ such that $|f(u)-f(v)|\ge p$, if $dist(u,v)=1$ and $|f(u)-f(v)|\ge q$, if $dist(u,v)=2$. This concept has been widely studied as it models some channel assignment problems. Intuitively, very close transmitters get very far apart frequencies (at distance at least $p$) and close transmitters get far apart frequencies (at distance at least $q$. It generalizes classical colouring concept as an $L(1,0)$-labelling of a graph is a proper colouring and an $L(1,1)$-labelling is a proper colouring of its square. More generally, if $G=(V,E)$ is a graph and $F$ is a subset of edges, a $(p,q)$-backbone colouring} of $(G,F)$ is a positive integer assignment~$f$ such that $|f(u)-f(v)|\ge p$, if $uv\in F$ and $|f(u)-f(v)|\ge q$, if $uv\in E$. In the particular case when $G$ is the square of the graph $H=(V,F)$, then a $(p,q)$-backbone colouring} of $(G,F)$ is an $L(p,q)$-labelling of $H$. In this talk, I will survey some results on $L(p,q)$-labelling and backbone colouring and present many related conjectures and problems.

• Data/horário: 25/03/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrantes: Manoel Campelo, Phablo Moura e Marcio Costa (MDCC, UFC)
• Título: Número k-cromático de webs e anti-webs
• Resumo:Uma k-coloração é uma coloração própria dos vértices de um grafo tal que cada vértice deve receber um conjunto de k cores e vértices adjacentes não podem partilhar nenhuma cor. O problema de encontrar o menor número de cores para o qual existe uma k-coloração, denominado de numero k-cromático, é NP-Dificl para um grafo qualquer. Vários resultados tem surgido sobre esse  problema para várias classes de grafos, assim como limites para os valores dos numeros k-cromáticos de uma série de grafos, como grafos perfeitos e uma caracterização interessante desse problema sobre o produto lexicográfico de um grafo. Nós exibiremos o valor do numero k-cromático pra um classe de grafo que de certa maneira generaliza os ciclos e anti-ciclos, além de outros resultados sobre limites do problema para outras classes de grafos.

• Data/horário: 18/03/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dr. Carlos Diego Rodrigues
• Título: Resolução do problema da mochila quadrático através da t-linearização
• Resumo:Apresentamos neste trabalho um método de resolução exata para o problema da mochila quadrático 0-1 (Quadratic Knapsack Problem – QKP), que consiste na maximização de uma função pseudo-booleana com coeficientes não-negativos sujeita a uma restrição de capacidade linear. Esta resolução é baseada em uma das técnicas mais comuns de tratamento dos problemas quadráticos: a linearização. Porém, ao contrário das linearizações tradicionais, que envolvem a adição O(n*n) novas variáveis, a linearização apresentada consiste na inclusão de uma única nova variável! Resultados computacionais revelam que este esquema de resolução está entre os melhores para o QKP.

• Data/horário: 11/03/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Michael Souza (DEMA, UFC)
• Título: Otimização para o Problema Geométrico da Diistância Molecular (MDGP)
• Resumo: A espectroscopia de ressonância magnética nuclear (RMN) fornece uma valiosa informação para o cálculo da estrutura tridimensional de proteínas: uma rede de distâncias envolvendo pares de átomos espacialmente próximos. No problema geométrico da distância molecular (MDGP), busca-se determinar uma conformação molecular tridimensional que satisfaça as restrições associadas às distâncias obtidas via RMN. Dadas a não-diferenciabilidade dos modelos relacionados e a existência de inúmeros mínimos locais, a obtenção de soluções globais para instâncias do MDGP com métodos clássicos de otimização é um problema desafiador. De fato, o MDGP pertence à classe NP-difícil. Neste seminário, faremos uma revisão sobre alguns problemas relacionados ao MDGP e apresentaremos uma proposta baseada em métodos aproximativos para sua resolução.

• Data/horário: 04/03/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Críston Souza (UFC, Quixada)
• Título: Políticas Eficientes para Revisitação de Páginas Web
• Resumo: Uma máquina de busca precisa constantemente revisitar páginas Web para manter seu repositório local atualizado. Uma política de revisitação deve ser empregada para construir um escalonamento de revisitações que mantenha o repositório o mais atualizado possível utilizando os recursos disponíveis. Para evitar sobrecarga de servidores Web, a política de revisitação deve respeitar um tempo mínimo entre requisições consecutivas a um mesmo servidor. Esta regra é chamada restrição de politeness. Devido ao porte do problema, consideramos que uma política de revisitação é eficiente se o tempo médio para escalonar uma revisitação é sublinear no número de páginas do repositório. Neste sentido, quando a restrição de politeness é considerada, não conhecemos política eficiente com garantia teórica de qualidade. Nesta pesquisa investigamos três políticas eficientes que respeitam a restrição de politeness, chamadas MERGE, RANDOM e DELAYED. Fornecemos fatores de aproximação para o nível de atualização do repositório quando empregamos as política MERGE ou RANDOM. Demonstramos que 0,77 é um limite inferior para este fator de aproximação quando empregamos a política RANDOM, e apresentamos uma conjectura de que 0,927 é um limite inferior para este fator de aproximação quando empregamos a política MERGE. As políticas também são avaliadas através da simulação da execução destas políticas para manter o nível de atualização de um repositório contendo 14,5 milhões de páginas Web. Um repositório contendo artigos da Wikipedia também é utilizado nos experimentos, onde podemos observar que a política MERGE apresenta melhores resultados que uma estratégia gulosa natural para este repositório. A principal conclusão desta pesquisa é que existem políticas simples e eficientes para o problema de revisitação de páginas Web, que perdem pouco em termos do nível de atualização do repositório mesmo quando consideramos a restrição de politeness.

• Data/horário: 25/02/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Rudini Sampaio (DC, UFC)
• Título: Partição de grafos em cliques e conjuntos independentes
• Resumo: Uma cocoloração de um grafo não é uma coloração feita por um gago ou por uma galinha cacarejando. Na verdade, é uma coloração onde cada classe de cor induz um conjunto independente ou uma clique. O número cocromático $z(G)$ de um grafo $G$ é o menor número $k$ tal que $G$ possui uma cocoloração com $k$ cores. Neste seminário, mostramos que obter o número cocromático é polinomial para grafos P4-laden estendidos e grafos $(q,q-4)$. Este é um trabalho conjunto com Sulamita Klein, Fábio Protti, Loana Nogueira e Raquel Bravo.

• Data/horário: 18/02/2011 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dra. Ana Shirley F. Silva
• Título: Duas conjecturas sobre o número b-cromático de grafos sem K_{2,3}
• Resumo: Dado um grafo $G$, uma b-coloração $\psi$ de $G$ é uma coloração onde, em cada cor $c$ de $\psi$, existe ao menos um vértice colorido com $c$ que é adjacente a cada outra cor em $\psi$ diferente de $c$. O número b-cromático $\chi_b(G)$ de $G$ é a quantidade máxima de cores utilizadas em uma b-coloração de $G$. Tal problema foi introduzido por Irving e Manlove, onde eles também provam que encontrar o número b-cromático de um grafo qualquer é NP-difícil. Neste mesmo artigo, eles fornecem um limite superior para o número b-cromático de um grafo $G$: se $m(G)$ é definido como o maior inteiro $k$ tal que $G$ tem ao menos $k$ vértices de grau ao menos $k-1$, então $\chi_b(G)\leq m(G)$. Este valor é chamado de m-grau de $G$. Irving e Manlove então mostram que a diferença entre o número b-cromático e o m-grau de um grafo qualquer pode ser arbitrariamente grande e que é no máximo 1 para árvores. Neste seminário, iremos discutir sobre duas conjecturas que sugerem que a diferença entre $m(G)$ e $\chi_b(G)$ é também limitada por 1 para certos grafos sem $K_{2,3}$ (não necessariamente induzido).

2010

• Data/horário: 10/12/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dra. Cristiana Huiban
• Título: Round Weighting Problem and gathering in wireless networks with symmetrical interference
• Resumo: We consider the problem of gathering information in a gateway in a radio mesh access network. Due to interferences, calls (transmissions) cannot be performed simultaneously and we define a round as a set of non-interfering calls. We model this problem as a Round Weighting Problem (RWP) in which the objective is to minimize the overall period of non-interfering calls activations (total number of rounds) providing enough capacity to satisfy the throughput demand of the nodes. We present generic methods to obtain lower and upper bounds for general graphs. More precise results are obtained considering a symmetric model of interference based on distance of graphs, called the distance-d model; the particular case d=1 corresponds to the primary node model, where two calls interfere only if they are adjacent. Then, this work focuses on the case where the network topology is a grid, presenting both lower bounds and various routing methods which meet the lower bounds, therefore getting optimal solutions. Different cases are considered according to the position of the gateway, the repartition of the demands and the integrality assumptions. In particular, we obtain closed formulae for uniform demands.

• Data/horário: 03/12/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Rafael Barbosa
• Título: Approximation results on the Pure Parsimony Haplotyping Problem
• Resumo: The Pure Parsimony Haplotyping Problem, which consists of finding pairs of haplotypes from genotype data under the parsimony criteria, is of high interest in current human genomics. In the present paper we introduce a new algorithm for the problem, which, under certain assumption on the input, yields the first constant factor approximation algorithm for the Pure Parsimony Haplotyping Problem. In addition, we show that there are instances of the problem that meet the previously known lower bound on the problem and, also, an inapproximability bound for the problem.

2009

• Data/horário: 12/11/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Albert Einstein Fernandes Muritiba (DEMA, UFC)
• Título: Fair Layout Optimization Problem – FLOP
• Resumo: A relevant logistic issue in the organization of a fair is to determine how stands have to be placed in the exhibition space so as to satisfy all constraints on security, ease of access, services, and so on, while maximizing the revenues coming from the exhibitors. We consider in particular the problem of allocating the maximum number of stands by satisfying all the constraints required by practical implementations. We examine a number of real world-cases, and show how basic mathematical programming models can be adapted to handle specific requests from the organizers. We report the solutions obtained through an original decision support system that embeds a number of algorithms to solve the various cases by reduction to one or more linear programs.

• Data/horário: 20/09/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Matej Stehlik (Université Grenoble, France)
• Título: Applications of the Borsuk-Ulam Theorem in combinatorics
• Resumo: The Borsuk-Ulam Theorem is a result from algebraic topology with interesting applications in combinatorics. Perhaps the best-known version states that for every continuous function f from the n-dimensional sphere to the n-dimensional Euclidean space, there exists a point x on the sphere such that f(x)=f(-x). A real-world example for the case n=2 is when we deflate a ball, and then proceed to crumple and flatten it: there is always a pair of points that were antipodal when the ball was inflated, but now are touching each other. The purpose of this informal mini-course is to show you some applications of the Borsuk-Ulam Theorem (and related results) in combinatorics. I will therefore not prove the theorem, and concentrate instead on the applications: multicoloured partitions of points, dividing a necklace between thiefs, and the chromatic number of Kneser graphs.

• Data/horário: 30/04/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Álinson Santos (aluno mestrado, MDCC, UFC)
• Título: Um Estudo do Politopo do Maior Subgrafo Induzido k-Partido
• Resumo: Um conjunto de vértices de um grafo é independente se este conjunto não contém nenhum par de vértices vizinhos. Grafos cujos vértices podem ser particionados em k conjuntos independentes são denominados grafos k-partidos. O Problema do Maior Subgrafo Induzido k-Partido consiste em encontrar, em um grafo de entrada, um subgrafo k-partido com a maior quantidade possível de vértices. Neste trabalho, apresentamos uma formulação linear inteira para este problema, baseada na formulação de representantes de cor, e fazemos um estudo preliminar do politopo associado: demonstramos algumas de suas propriedades básicas, como dimensão; descrevemos algumas de suas faces mais simples; mostramos que algumas de suas faces são isomórficas a politopos associados a seus subgrafos; que algumas outras são isomórficas a politopos do Problema do Maior Conjunto Independente; e que é possível obter, a partir da descrição de facetas destas faces isomórficas, a descrição de facetas do politopo original, através de lifting.

• Data/horário: 09/04/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Nicolas Nisse (Sophia-Antipolis, France)
• Título: Graph Searching
• Resumo:Graph Searching

• Data/horário: 12/03/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Manoel Campelo (DEMA, UFC)
• Título: The Chvatal closure of generalized stable sets in bidirected graphs
• Resumo:We consider the set of integral solutions of $Ax\leq b$, $x\geq 0$, where $A$ is the edge-vertex incidence matrix of a bidirected graph. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvatal closure in this case. Joint work with Gerard Cornuejols.

• Data/horário: 05/03/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Rafael Andrade (DEMA, UFC)
• Título: Multiservice Multifacility Network Design under Uncertainty
• Resumo:The problem of designing high speed networks using different modular link capacities, in the same model, in order to met uncertain demands obtained from different probability distribution functions (PDF) is a very hard and challenging real network design problem. In this work we present the problem formulation and report computational results using branch-and-bound and Benders decomposition solution approaches. The network traffic is generated from three main classes of uncertain demands (multiservice) simulated from different PDF, including heavy tailed ones. We use up to three different types of modular capacities (multifacilities), since it seems that using more than this can lead to an intractable model while the gain in solution quality is very poor. The objective is to minimize penalty (in case of unmet demands) and investment costs. We give 95\% confidence intervals on the expected optimal solution for the resulting two-stage stochastic integer problem. In our computational results we use a subset of the Brazilian Ypê backbone network. The evidences show that our model can handle real instances, but the computational effort should be very high in obtaining solutions for the problem.

• Data/horário: 11/01/2010 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Rudini Sampaio (DC, UFC)
• Título: Property Testing and Parameter Testing for Permutations
• Slides
• Resumo:There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called “property testing” and “parameter testing”, where a property or parameter is said to be “testable” if it can be estimated accurately in this way. The algorithmic appeal is evident, as this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations. We give a permutation counterpart of a famous result by Alon and Shapira stating that every monotone graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in the unit square, which in turn may be used to define a new model of random permutations.

• Data/horário: 09/10/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Tibérius Bonates (Rutgers Center for Operations Research)
• Título: Modelos de Otimização para Construção de Classificadores Baseados em Regras
• Slides
• Resumo: Apresentaremos Modelos de Otimização para Construção de Classificadores Baseados em Regras

• Data/horário: 18/09/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Profa. Dra. Rafael Andrade (DEMA, UFC)
• Título: Árvore com limite inferior de conectividade em nós centrais
• Resumo: Uma rede de comunicação e supervisão de dados com topologia em árvore pode ser vista como um subgrafo acíclico $T=(V(T),E(T))$ de um grafo $G=(V,E)$, em que $V$ representa o conjunto de nós da rede e $E$, o conjunto de arestas conectando diretamente elementos de $V$, com $V(T)= V$ e $E(T)\subset E$. Em uma rede em árvore $T$ distinguimos dois tipos de nós, os externos (folhas, terminais) e os internos (centrais, servidores). O elevado custo dos equipamentos que possibilitam um determinado nó funcionar como nó central (supervisor) em $T$ origina uma preocupação prática no projeto de redes de comunicação e supervisão de dados, de forma que atribuir essa tarefa a um dado nó de $T$ só é vantajoso se o mesmo for conectado (supervisionar) a um número mínimo de nós da rede. Valor esse previamente conhecido em função de características técnicas dos equipamentos a serem empregados para que um nó tenha a função de nó central. Vale ressaltar que antes de se determinar o melhor projeto para uma rede $T$, todos os nós são indistinguíveis e não se conhece nem quantos nem quais nós serão centrais ou terminais. Assim, o objetivo desse problema é, respeitando a condição para um nó ser central, encontrar a topologia em árvore $T$ de custo mínimo. Esse problema é NP-difícil e pouco se conhece sobre o mesmo na literatura. Em nosso seminário discutiremos formulações matemáticas de programação inteira para esse problema e empregar técnicas de otimização combinatória (baseadas em relaxação Lagrangeana, decomposição de Benders, método do subgradiente e de \emph{branch-and-bound}) para desenvolver algoritmos heurísticos e exatos para sua resolução. Porém, como a pesquisa está em fase inicial de desenvolvimento, o enfoque principal do seminário será baseado em subproblemas gerados para a decomposição de Benders (formulação, evidência de complexidade, exemplos).

• Data/horário: 28/08/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Profa. Dra. Celina Figueiredo (UFRJ)
• Título: The P vs. NP-complete dichotomy of some challenging problems in graph theory
• Resumo: The Clay Mathematics Institute has selected seven Millennium Problems to motivate research on important classic questions that have resisted solution over the years. Among them is the central problem in theoretical computer science: the P vs. NP problem, which aims to classify the possible existence of efficient solutions to combinatorial and optimization problems. The main goal is to determine whether there are questions whose answer can be quickly checked, but which require an impossible long time to solve by any direct procedure. In this context, it is important to determine precisely what facet of a problem makes it NP-complete. We shall discuss our contribution to the P vs. NP-complete dichotomy through the classification of some long-standing problems in important areas of graph theory: perfect graphs, intersection graphs, and structural characterization of graph classes. More precisely, we have shown that Chvatal’s SKEW PARTITION is polynomial and that Roberts-Spencer’s CLIQUE GRAPH is NP-complete. We have also solved the dichotomy for Golumbic-Kaplan-Shamir’s SANDWICH problem. We shall describe two examples where we can determine the full dichotomy: The edge-coloring problem for graphs with no cycle with a unique chord, and the three nonempty part sandwich problem. Open problems are discussed: the stubborn problem for list partition; the chromatic index of chordal graphs; the recognition of split clique graphs.

• Data/horário: 21/08/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dorian Mazauric (INRIA, I3S(CNRS/UNS), Sophia Antipolis, France)
• Título: On rerouting in optical networks
• Slides
• Resumo: In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of preestablished connections. However, such a policy leads to a poor usage of resources and so higher blocking probability: new connection requests might be rejected while network resources are sufficient to serve all the traffic. Therefore, it is important to regularly reconfigure the network by rerouting established connections in order to optimize the usage of network resources. We consider the network reconfiguration problem that consists in switching existing connections one after the other from the current routing to a new pre-computed routing. We assume that each connection uses the entire capacity of each link, each having capacity one. Due to cyclic dependencies between connections, some requests may have to be temporarily interrupted during this process. Clearly, the number of requests simultaneously interrupted has to be minimized. Furthermore, it might be impossible for the network operator to interrupt some connections because of the contract signed with the corresponding clients. In this setting, the network reconfiguration problem consists in going from a routing to another one given that some priority connections cannot be interrupted. The network reconfiguration problem without priority connections has previously been modeled as a cops-and-robber game in [1] [2]. This problem corresponds to capture an invisible and fast fugitive in a digraph, called dependency digraph in [3], using the minimum number of agents. This minimum number of agents is the process number of the digraph and it corresponds to the minimum number of requests that have to be simultaneously interrupted. Since the problem of computing the process number of a digraph is NP-Hard, we have designed heuristic algorithms for this problem [4]. We have extended this model to handle priority connections. Then we have identified cases where no solution exists [4]. Using a simple transformation, we have proved that the reconfiguration problem with priority connections can be reduced to the problem without this constraint. Furthermore we have designed a distributed algorithm to compute the process number when the digraph is a (symmetric) tree [5], and we have proved that if each request uses now one third of the capacity of each link of its path, then the problem of deciding if the generalized process number
  is 0 is NP-Complete [6]

• Data/horário: 14/08/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Profa. Dra. Cláudia Linhares Sales (DC, UFC)
• Título: Coloração Gulosa de Produtos de Grafos
• Resumo: De forma análoga a estudos feitos sobre o número cromático do produto de dois grafos em função dos números cromáticos dos mesmos, fazemos um estudo sobre o número cromático guloso do produto de um grafo em função dos número cromáticos dos mesmos. Apresentamos limite inferior e superior para o número cromático guloso de produtos lexicográficos e discutiremos algumas questões sobre esses limites nos produtos cartesiano e direto. Esse trabalho foi feito em colaboração com M. Asté e F. Havet.

• Data/horário: 05/06/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Fabricio Siqueira Benevides (aluno doutorado, University of Memphis)
• Título: Uso do Lema da Regularidade de Szmeredi em problemas de Ramsey para circuitos
• Slides
• Resumo: Suspense

• Data/horário: 08/05/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Profa. Dra. Cláudia Linhares Sales (DC, UFC)
• Título: Grafos b-perfeitos
• Resumo: Quando não se sabe colorir um grafo otimamente em tempo polinomial, tenta-se melhorar uma coloração qualquer do grafo afim de se aproximar do seu número cromático. Diversos métodos para executar essas melhorias são utilizados. É estudo relevante saber qual é a pior coloração, em termos do números de cores utilizadas, que se pode obter mesmo depois de efetuada a melhoria de deslocamento de vértices. Esse maior número cores é número b-cromático de um grafo. Os grafos b-perfeitos foram recentemente definidos como uma tentativa entender as estruturas de um grafo que afetam o seu número b-cromático. Nesse seminário apresentaremos os grafos b-perfeitos, uma conjectura sobre uma caracterização dessa classe de grafos e alguns resultados parciais

• Data/horário: 21/04/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Júlio Araújo (aluno mestrado, MDCC, UFC)
• Título: Grafos direcionados acíclicos com a propriedade de caminho direcionado único
• Resumo:Dados um grafo direcionado $G$ e uma família $P$ de caminhos direcionados de $G$, dizemos que uma carga de um arco é a quantidade de caminhos de $P$ que contém esse arco. O maior valor de carga de um arco de $G$ é denotado por $\pi(G,P)$. Denotamos por $\omega(G,P)$ a menor quantidade de cores necessárias para colorir os caminhos de $P$ de tal modo que se dois caminhos compartilham um mesmo arco eles devem receber cores disjuntas. O grafo conflito $H = C(G,P)$ é tal que, para cada caminho de $P$, existe um vértice associado em $H$ e, se dois caminhos em $P$ compartilham pelo menos um arco, então existe uma aresta entre seus vértices correspondentes em $H$. Bermond et al. estudaram a relação entre $\pi(G,P)$ e $\omega(G,P)$ em grafos denotados por UPP-DAGs, ou seja, grafos direcionados acíclicos nos quais cada par de vértices possui no máximo um caminho direcionado entre eles. Além disso, eles introduziram um novo problema em grafos denotado por “boa atribuição de rótulos”. Um grafo $G$ admite uma boa atribuição de rótulos se podemos atribuir valores reais distintos às suas arestas de tal modo que não existem dois caminhos com rótulos crescentes entre dois vértices de G. Bermond et al. relacionaram o estudo deste problema em grafos conflito $H=C(G,P)$ com o estudo dos parâmetros anteriormente citados em UPP-DAGs $G$ com famílias $P$ de caminhos direcionados.
  Nesta apresentação, falarei dos resultados deste trabalho de Bermond et al. e comentarei alguns resultados obtidos por mim, N. Cohen, F. Giroire e F. Havet sobre este problema de boa atribuição de rótulos.

• Data/horário: 17/04/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Victor Campos (aluno doutorado, MDCC, UFC)
• Título: Construindo a Organização Terrorista Perfeita
• Resumo: Uma transversal em uma árvore enraizada é um conjunto de nós que intersecta qualquer caminho da raiz a uma folha. Denote por $c(T,k)$ o número de transversais de tamanho $k$ em uma árvore enraizada $T$. Se $T$ e $T’$ são árvores com $n$ vértices, dizemos que $T’$ é mais robusta que $T$ se $c(T,k)\geq c(T’,k)$ para todo $1\leq k\leq n$ e $c(T,k)>c(T’,k)$ para pelo menos um destes valores de $k$. Mostramos algumas operações em ávores que a transformam numa árvore mais robusta. Utilizamos estas operações para mostrar a estrutura da árvore mais robusta com a restrição de grau máximo nos vértices. Relacionamos os resultados de transversais em árvores ao problema de construir uma organização terrorista perfeita. Este resultado é um trabalho meu em conjunto com V. Chvátal, L. Devroye e P. Taslakian.

• Data/horário: 27/03/2009 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Prof. Dr. Rudini Sampaio (DC, UFC)
• Título: Uma Caracterização Combinatória para Propriedades Testáveis de Grafos
• Slides
• Resumo: Dizemos que um grafo $G$ é $\varepsilon$-far( $P$ ) se mais de $\varepsilon n^2$ arestas de $G$ devem ser modificadas para que $G$ satisfaça uma propriedade $P$. Um Testador para $P$ é um algoritmo aleatório que realiza consultas nas arestas e distingue com alta probabilidade se $G$ satisfaz $P$ ou é $\varepsilon$-far( $P$ ). Diz-se que $P$ é Testável se possui um Testador que realiza $q(\varepsilon)$ consultas, que independe do tamanho da entrada. Vários resultados sobre propriedades testáveis foram obtidos: livre de triângulo, $k$-colorabilidade. Neste paper de Alon-Fischer-Newman-Shapira mostra-se que tipo de propriedades são testáveis, uma caracterização baseada no famoso Lema da Regularidade de Szemerédi.

2008

• Data/horário: 13/03/2008 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dr. Abdel Lisser (Université de Paris Sud, Orsay, France)
• Título: Knapsack problem with random weights
• Resumo: We present different extensions of the knapsack problem to the case where different elements of the problem formulation are subject to a degree of uncertainty described by random variables. This brings the knapsack problem into the realm of stochastic programming. Different model formulations are proposed, based on the introduction of probability constraints. The first one is a static quadratic knapsack with a probability constraint on the capacity of the knapsack. The second one is a two-stage quadratic knapsack model, with recourse, where we introduce a probability constraint on the capacity of the knapsack in the second stage. The solution techniques are based on the semidefinite relaxations. Both discrete and continuous relaxations are considered. Results of numerical experiments are discussed.

• Data/horário: 26/03/2008 – 16:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dr. Gérard Plateau (Université Paris 13)
• Título: Le sac à dos avec réoptimisation pour la résolution du dual Lagrangien du bi-knapsack en variables 0-1.
• Resumo: On envisage la relaxation Lagrangienne du sac à dos à deux contraintes en 0-1, par dualisation de l’une de ses deux contraintes. Une méthode de sous-gradients dédiée à la résolution du dual Lagrangien associé nécessite la résolution d’une suite de problèmes de sac à dos 0-1 avec contrainte invariante mais dont l’objectif évolue avec la suite des multiplicateurs de Lagrange engendrés. Une accélération de la méthode de sous-gradients est obtenue lorsque des techniques de réoptimisation sont envisagées pour les problèmes de sac à dos de fin de procédure (des multiplicateurs très proches engendrent des sac à dos très voisins). La méthode BPK pour la résolution exacte du sac à dos 0-1 est d’abord rappelée : prétraitement de complexité linéaire (résolution en continu, heuristique gloutonne, fixation de variables via la relaxation lagrangienne) suivi d’une phase d’énumération qui fait coopérer le branch-and-bound et la programmation dynamique). L’heuristique Lagrangienne MARIE (Method combining Approximation and Reoptimization for Integer programming Evoluating instances) pour le biknapsack 0-1 est ensuite présentée : elle intègre la notion de réoptimisation mais aussi une recherche locale et une fixation de variables du problème global. Cette méthode MARIE a été testée sur un échantillon de vingt instances de biknapsack à 1000 variables 0-1, dont les données corrélées sont générées aléatoirement. Elle permet d’obtenir des écarts de dualité presque nuls en de faibles temps de calcul (temps moyen inférieur à 2,4 secondes sur une station SUN Ultra 5).

• Data/horário: 29/02/2008 – 14:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Dr. Colin McDiarmid (Department of Statistics, University of Oxford, Inglaterra)
• Título: Random graphs from a minor-closed class

• Data/horário: 29/02/2008 – 15:00h.
• Local: Sala 01, Bloco 915
• Palestrante: Stéphan Thomassé (LIRMM, Université de Montpellier, França)
• Título: Graph Searching and Sub-modular Partition Functions

• Data/horário: 29/02/2008 – 16:30h.
• Local: Sala 01, Bloco 915
• Palestrante: Dr. Bruce Reed (McGill University, Montreal, Canadá)
• Título: Graph Colouring via the Probabilistic Method