O problema da subsequência comum máxima sem repetições

• Ano de defesa: 2010
• Autor(a) principal: Tjandraatmadja, Christian
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: algoritmos de aproximação; approximation algorithms; branch-and-cut; combinatória poliédrica; heurísticas; heuristics; integer programming; longest common subsequence; polyhedral combinatorics; programação inteira; repetition-free longest common subsequence; subsequência comum máxima; subsequência comum máxima sem repetições
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo.