• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Programação matemática e imersões métricas para aproximações em problemas de corte

    Thumbnail
    View/Open
    R - D - SANTIAGO VIERTEL.pdf (978.9Kb)
    Date
    2014
    Author
    Viertel, Santiago
    Metadata
    Show full item record
    Subject
    Dissertações
    Ciência da computação
    xmlui.dri2xhtml.METS-1.0.item-type
    Dissertação
    Abstract
    Resumo: Os algoritmos de aproximação são capazes de gerar soluções próximas da ótima demandando tempo de execução polinomial. Vários dos algoritmos de aproximação existentes na literatura solucionam problemas com base em valores numéricos obtidos em soluções de programas matemáticos, como programas lineares e programas vetoriais. Os problemas do corte máximo, do corte multisseparador mínimo e do corte mais disperso podem ser modelados com programas matemáticos inteiros que, se solucionados, resultam em soluções átimas. Porem, solucionar programas matemáticos inteiros demanda tempo exponencial exigindo, assim, que sejam criados novos programas matemáticos por meio de relaxações. Uma relaxação admite valores contínuos de solução, o que torna possível encontrar a solução ótima do programa relaxado em tempo polinomial. Em contrapartida, para que sejam encontradas soluções próximas da ótima, faz-se necessárias tomadas de decisão baseadas em análises sobre as soluções dos programas relaxados. Os três problemas apresentados são modelados por programas matemáticos relaxados e solucionados com algoritmos desenvolvidos com base em análises geométricas sobre as soluções desses programas. As soluções dos programas lineares relaxados que modelam os problemas do corte multisseparador mínimo e do corte mais disperso são processadas e são visualizadas como pontos cujas distâncias são calculadas pela norma 1. Sub-rotinas que imergem espaços métricos finitos gerais em espaços métricos definidos pela norma l1 se mostraram importantes no desenvolvimento de algoritmos de aproximação. Para solucionar o problema do corte mais disperso, são utilizados algoritmos de imersão que possuem uma certa taxa de distorção das distâncias, sendo essa taxa o principal fator para a determinação da garantia de aproximação do algoritmo como um todo.
     
    Abstract: Approximation algorithms can generate near optimal solutions requiring execution in polynomial time. Many approximation algorithms in the literature follow the idea of searching for numerical values from mathematical programming formulations, usually linear or vector programming, of the problem in consideration. The problems of maximum cut, multiway cut and sparsest cut can be modeled with integer mathematical programs that result in optimal solutions. However, solving an integer mathematical program is a NP-hard problem, so an usual approach is the creation of new mathematical programs through relaxations. A relaxation admits continuous solution, which makes possible to find the relaxed program optimal solution in polynomial time. However, in order to find near optimal solutions one should perform an analyses of this solution obtained by relaxed programs. The three problems presented here are modeled by relaxed mathematical programs and solved by algorithms based on geometric analyses on the solutions of these programs. The solutions of the relaxed linear programs that model the problems of the multiway cut and the sparsest cut are seen as points whose distances are calculated by the l1 norm. Subroutines that embed general finite metric spaces in metric spaces defined by the l1 norm proved to be important in approximation algorithms. In order to solve the sparsest cut problem, the approach is using embedding algorithms that have a certain distortion rate of the distances, being this rate the main factor determining the performance guarantee of the algorithm.
     
    URI
    http://hdl.handle.net/1884/36110
    Collections
    • Dissertações [355]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV