Un algoritmo aproximado para el problema de cobertura mínima de costo único

  • Duración Inicio: 26/10/2012 Fin: 27/09/2013
  • Tipo de Investigación Básica
  • Resumen del Proyecto

    En general las soluciones exactas para el unicost set cover problem se obtienen a través de algoritmos intratables pues el problema es NP. Hay diferentes algoritmos aproximados de tipo polinomial. Por ejemplo el conocido algoritmo estándar de Johnson que utiliza la técnica Greedy. Presentamos un algoritmo aproximado que implementa la reducción de redundancias, la utilización de disyunciones y una métrica, para deseleccionar subconjuntos, en base a sus deméritos. El mismo parece comportarse bastante bien para los experimentos realizados, en comparación con el estándar e incluso con otros algoritmos aproximados.

  • Impacto

    • Recopilación documental, selección y análisis.
    • Análisis de recurrencias, análisis de algoritmos.
    • Análisis de recurrencias, análisis de algoritmos, programación dinámica, divide y vencerás, greedy, pruebas experimentales, esquemas usuales de demostración (inducción, reducción al absurdo), deducción, preprocesamiento, estructuras avanzadas de datos.

    • Objetivos

  • Objetivo General

    • Optimizar un set de algoritmos sobre secuencias, en lo relativo a sus factores constantes
  • Objetivos Especificos

    • Participantes

  • Coordinador Lucio Torrico Díaz
  • Co-cordinador
  • - Participantes del proyecto
    Nombre Grado Académico Cargo Cédula de identidad
    		Maestria Coordinador
    ()
  • - Colaboradores del proyecto
    Nombre Grado Académico Cargo Cédula de identidad

    • Unidades Participantes

  • Unidad Proponente Instituto de Investigación en Informática
  • Unidad Contraparte
  • + Unidades Co-Ejecutoras
    Nombre de la Unidad Responsable de la Unidad

    • Lineas de Investigación

    • Diseño y Desarrollo de Sistemas