Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-04-20T13:39:42Z No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-30T17:25:56Z (GMT) No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Made available in DSpace on 2016-05-30T17:25:56Z (GMT). No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Translocações são usadas para mensurar a distância evolutiva entre espécies. Do ponto de vista biológico dois tipos de genomas tem recebido atenção: genomas com e sem sinal. Ao considerar genomas com sinal, computar a distância mínima de translocações é linear enquanto que o caso sem sinal é NP-difícil. Propõem-se algoritmos genéticos (AGs) para resolver o problema de distância de translocação entre genomas sem sinal. A abordagem, consiste em utilizar uma população composta por indivíduos representando genomas com sinal obtidos de um genoma sem sinal provido como entrada. A solução de cada indivíduo é também uma solução admissível para o genoma dado. A função de aptidão utilizada, que é a distância para genomas com sinal, é computada linearmente com um algoritmo proposto por Bergeron et al. O AG baseado nessa abordagem foi aprimorado com duas técnicas de otimização: memética e aprendizagem baseada em oposição. Além disso, foram propostas paralelizações do AG memético buscando diminuir o tempo de processamento assim como melhorar a precisão. A qualidade dos resultados foi validada utilizando uma implementação de um algoritmo de raio de aproximação 1.5+" recentemente proposto por Cui et al. Experimentos foram realizados tomando como entrada genomas sintéticos e gerados a partir de dados biológicos. Os AGs forneceram melhores resultados que o algoritmo de controle de qualidade. As paralelizações apresentaram melhoras tanto no tempo de execução quanto na precisão dos resultados. Utilizou-se o teste de hipóteses de Wilcoxon a fim de verificar a significância estatística das melhorias fornecidas pelos AGs aprimorados em relação àquelas fornecidas pelo AG básico. Desta análise foi possível identificar que o AG memético provê resultados diferentes (melhores) que o AG básico, e que este último e o AG com aprendizagem baseada em oposição não apresentam nenhuma diferença significativa. O teste foi também aplicado para comparar as soluções das paralelizações confirmando que existem aprimoramentos dos resultados comparados com o AG memético. _______________________________________________________________________________________________ ABSTRACT / Translocations are used to measure the evolutionary distance between species. From a biological point of view two types of genomes have received attention: signed and unsigned genomes. When considering signed genomes, the problem can be solved in linear time, while, in the case of unsigned genomes the problem was shown to be NP-hard. Genetic algorithms (GAs) are proposed to solve the translocation distance problem between unsigned genomes. The approach consists in using a population composed of individuals representing signed genomes obtained from a given unsigned genome provided as input. The solution of each individual is also an admissible solution to the given genome. The fitness function used, which is the distance for signed genome, is computed linearly with an algorithm proposed by Bergeron et al. The GA based on this approach has been enhanced with two optimization techniques: memetic and opposition based learning. Also, parallelizations of the GA embedded with memetic were proposed seeking to improve both running time as the accuracy of results. The quality of the results was verified using an implementation of a 1.5+"-approximation algorithm recently proposed by Cui et al. Experiments were performed taking as input synthetic genomes and genomes generated from biological data. The GAs provided better results than the quality control algorithm. The parallelizations showed improvements both regarding runtime as well as accuracy. A statistical analysis based on the Wilcoxon test was performed to check if the improvements in the solutions provided by enhanced GAs compared to those provided by the basic GA have some significance. This analysis can identify that the GA embedded with the technical memetic provides different (better) results than GA and that the results provided by the GA embedded with opposition based learning presents no significant difference. The test was also performed to compare the solutions of the parallelizations confirming that there are improvements of the results regarding the GA embedded memetic.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

Neste trabalho, objetivamos apresentar o Teorema de Alon e Naor, o qual afirma que existe um algoritmo de aproximação para a norma de corte de uma matriz qualquer, sendo que a garantia de desempenho desse algoritmo é a inversa da constante de Grothendieck. Introduzimos a norma de corte de uma matriz e exibimos algumas de suas propriedades. Uma delas é que a norma de corte é equivalente a uma outra norma, que é valor ótimo de um programa inteiro quadrático que pode ser relaxado por um programa semidefinido. Além do Teorema de Alon e Naor, construímos mais dois algoritmos de aproximação para a norma de corte. Ambos possuem garantia de desempenho inferior que a do Teorema de Alon e Naor, porém as técnicas que foram utilizadas para obter tais algoritmos são interessantes. Enunciamos a Desigualdade e Grothendieck reformulada por Lindenstrauss e Pelcýnski e mostramos uma cota superior para a constante de Grothendieck que se baseia no Argumento de Krivine. Finalmente, apresentamos três aplicações do Teorema de Alon e Naor: em corte máximo de um grafo; na versão algorítmica do Lema da Regularidade de Szemerédi; e no Teorema de Frieze e Kannan. / In this work, our objective is to present Alon and Naor\'s Theorem, which states that there exists an approximation algorithm for cut-norm of any matrix and that the approximations guarantee of the algorithm is the inverse of the Grothendieck\'s constant. We introduce the cut-norm of a matrix and we show some of its properties. One is that the cut-norm is equivalent of some other norm which is the optimum value of quadratic integer program which can be relaxed for a semidefinite program. Beyond Alon and Naor\'s Theorem, we construct two more approximation algorithm for cut-norm. The approximation guarantee of both is inferior to the Alon and Naor\'s Theorem, but the techniques for obtaining such algorithms is interesting. We show Grothendieck\'s Inequality reformulated by Lindenstrauss e Pelcýnski and we show an upper bound for the Grothendieck\'s constant which is based on Krivine\'s Argument. Furthermore, we show three applications of Alon and Naor\'s Theorem: Maximum cut of a graph, an algorithmic version of Szemerédi Regularity Lemma, and Frieze and Kannan\'s Theorem.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:59:09Z (GMT). No. of bitstreams: 1 Reis_MarcioFelix_M.pdf: 1988657 bytes, checksum: 6ee5ea6ba406aea3ccb7e3332e679eab (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos / Abstract: In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Flávio Keidi Miyazawa, Maxim Sviridenko / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T09:17:37Z (GMT). No. of bitstreams: 1 Pedrosa_LehiltonLelisChaves_D.pdf: 3649302 bytes, checksum: 9f37cca5fca5af1697c2099c8e0f2798 (MD5) Previous issue date: 2014 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T23:02:27Z (GMT). No. of bitstreams: 1 Galvao_GustavoRodrigues_M.pdf: 1280667 bytes, checksum: 0809ad85a3b7f16ff5d7af5fc4124f0a (MD5) Previous issue date: 2012 / Resumo: Ao longo da evolução, mutações globais podem alterar a ordem dos genes de um genoma. Tais mutações são chamadas de eventos de rearranjo. Em Rearranjo de Genomas, estimamos a distância evolutiva entre dois genomas calculando-se a distância de rearranjo entre eles, que é o tamanho da menor sequência de eventos de rearranjo que transforma um genoma no outro. Representando genomas como permutações, nas quais os genes aparecem como elemento, à distância de rearranjo pode ser obtido resolvendo-se o problema combinatório de ordenar uma permutação utilizando o menor número de eventos de rearranjo. Este problema, que é referido como Problema da Ordenação por Rearranjo, varia de acordo com os tipos de eventos de rearranjo considerados. Nesta dissertação, focamos nosso estudo em dois tipos de eventos: reversões e transposições. Variações do Problema da Ordenação por Rearranjo que consideram esses eventos têm se mostrado difíceis de ser resolvida otimamente, por isso a maior parte dos algoritmos propostos - os quais denominamos genericamente por algoritmos de rearranjo de genomas - são aproximados e é esperado que os próximos avanços ocorram nesse sentido. Em razão disso, desenvolvemos uma ferramenta que avalia as respostas desses algoritmos. Para ilustrar sua aplicação, nós a utilizamos para avaliar as respostas de 16 algoritmos de rearranjo de genomas aproximados relativos a 6 variações do Problema da Ordenação por Rearranjo. Além da ferramenta, este trabalho traz outras contribuições. Desenvolvemos um algoritmo exato para calcular distâncias de rearranjo que é mais eficiente em termos de uso de memória do que qualquer outro algoritmo que encontramos na literatura. Apresentamos conjecturas que dizem respeito à forma como as distâncias de rearranjo se distribuem. Validamos conjecturas referentes ao diâmetro, que é o maior valor alcançável pela distância de rearranjo entre uma permutação qualquer e a identidade considerando-se todas as permutações com o mesmo número de elementos. Apresentamos demonstrações formais para o fator de aproximação de alguns dos algoritmos avaliados. Por fim, mostramos que os fatores de aproximação de 7 dos 16 algoritmos avaliados não podem ser melhorados, o que contradiz algumas hipóteses levantadas na literatura, e conjecturamos que os fatores de aproximação de outros 6 algoritmos também não possam / Abstract: During evolution, global mutations may modify the gene order in a genome and such mutations are called rearrangement events. In Genome Rearrangements, we estimate the evolutionary distance between two genomes by computing the rearrangement distance between them, which is the length of the shortest sequence of rearrangement events that transforms one genome into the other. Representing genomes as permutations, in which genes appear as elements, the rearrangement distance can be obtained by solving the combinatorial problem of sorting a permutation using a minimum number of rearrangement events. This problem is referred to as Rearrangement Sorting Problem and varies accordingly to the types of rearrangement events considered. In this dissertation, we focus on two types of rearrangement events: reversals and transpositions. Variants of Rearrangement Sorting Problem involving these events have been shown to be difficult to solve optimally, therefore most of the proposed algorithms - which we denominate generically as genome rearrangement algorithms - are approximations, which have been the expected direction to follow. For this reason, we developed a tool that evaluates the results of these algorithms. To illustrate its application, we used it to evaluate the results of 16 genome rearrangement algorithms regarding 6 variants of Rearrangement Sorting Problem. Besides this tool, we developed an exact algorithm for computing rearrangement distances that is more efficient in terms of memory than any algorithm we have found in literature. Additionally, we presented conjectures on how the rearrangement distance are distributed and validated them regarding their diameter, which is the greatest value that the rearrangement distance between a permutation and the identity can reach considering all permutations with the same number of elements. Moreover, we presented formal proofs on the approximation ratio of some of the evaluated algorithms and showed that the approximation ratio of 7 out of the 16 evaluated algorithms cannot be improved, which contradicts some hypothesis raised in literature. Lastly, we conjectured that the approximation ratio of another 6 algorithms also cannot be improved / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros. / The objective of this text is to study computational problems that emerge from the relation between graphs and bidimensional surfaces, giving special attention to the crossing number problem and graph drawings on books. We present a reduction from MULTICUT to CROSSING NUMBER, in addition to a complexity result on comparability graphs based on a known result about drawings on books.

Made available in DSpace on 2014-06-12T15:56:22Z (GMT). No. of bitstreams: 2 arquivo2919_1.pdf: 1890307 bytes, checksum: a778a46df2372bc90f89174a0b49fdda (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Patrulhar é o ato de andar ou viajar por uma área, em intervalos regulares, para protegê-la ou supervisioná-la. Informalmente, uma boa estratégia de patrulhamento é aquela que minimiza o tempo gasto entre duas visitas à mesma localização. Além de sua aplicação prática, o Problema da Patrulha Multiagentes (PMA) é um problema didático, pois compreende desde problemas computacionais simples, como a determinação do menor caminho entre dois pontos em um território até problemas mais complexos inerentes ao estudo de Sistemas Multiagentes (SMA). Para o estudo de SMAs, o PMA mostra-se rico, pois envolve várias características relevantes de um SMA como coordenação, comunicação, organização, negociação, conceitos de sociedades de agentes, entre outros. Em 2002, um trabalho pioneiro, realizado pelo grupo de Inteligência Artificial do Centro de Informática da Universidade Federal de Pernambuco, propôs as primeiras arquiteturas para o PMA e as avaliou empiricamente. Trabalhos posteriores propuseram soluções mais sofisticadas, como a utilização de negociação e aprendizagem, elaborando e avaliando uma maior quantidade de arquiteturas. Apesar dos trabalhos empíricos realizados, uma abordagem teórica do PMA se fazia necessária para a evolução na pesquisa do problema. Em cooperação com a Universidade Paris 6 na França, um primeiro estudo teórico do PMA foi proposto por Yann Chavaleyre e este motivou os resultados apresentados no nosso trabalho. Nosso objetivo na presente dissertação é desenvolver estratégias de patrulhamento e formalizar o PMA como problema de otimização. Mencionamos os trabalhos relacionados ao PMA existentes na literatura, adicionando inclusive os estudos mais recentes envolvendo estratégias de partições em grafos. Formalizamos o PMA como um problema de otimização NP (NP-Optimization Problem - NPO) bem como também exibimos uma prova de sua intratabilidade. Elaboramos e implementamos estratégias de patrulhamento a partir de algoritmos de aproximação e outras heurísticas para geração de partições conexas em grafo. Para o particionamento dos territórios, utilizamos soluções para o Problema do k-Centros Capacitado e o Problema das Partições Conexas Balanceadas. Implementamos também o algoritmo de aproximação desenvolvido por Chavaleyre com base na geração de partições a partir da árvore geradora de peso mínimo dos grafos a serem patrulhados. Realizamos vários experimentos no Simpatrol, simulador para sistemas multiagentes em tempo real, desenvolvido neste projeto de mestrado em um trabalho conjunto com o aluno Daniel Moreira. Também efetuamos análises comparativas dos resultados obtidos