Show simple item record

dc.date.accessioned2019-02-20T13:26:07Z
dc.date.available2019-02-20T13:26:07Z
dc.date.issued2015-05-01
dc.identifier.citationSoulignac, F. (Dir.) (2017). Algoritmos eficientes para problemas de grafos (Proyecto de investigación). Bernal, Argentina: Universidad Nacional de Quilmeses
dc.identifier.urihttp://ridaa.unq.edu.ar/handle/20.500.11807/973
dc.formatapplication/pdfes
dc.format.extent11 p.es
dc.languagespaes
dc.relationinfo:eu-repo/grantAgreement/UNQ/PUNQ I+D//AR. Buenos Aires. Bernal/Algoritmos eficientes para problemas de grafoses
dc.rightshttps://creativecommons.org/licenses/by/2.5/ar/es
dc.subjectGrafoses
dc.subjectOptimizaciónes
dc.subjectAlgoritmoses
dc.subjectMetaheurísticaes
dc.subjectComplejidad computacionales
dc.subjectProgramación lineales
dc.subjectGraphsen
dc.subjectOptimizationen
dc.subjectAlgorithmsen
dc.subjectMetaheuristicen
dc.subjectComputational complexityen
dc.subjectLinear programmingen
dc.subjectOtimizaçãopt
dc.subjectMeta-heurísticapt
dc.subjectComplexidade computacionalpt
dc.subjectProgramação linearpt
dc.titleAlgoritmos eficientes para problemas de grafoses
dc.typeinfo:ar-repo/semantics/proyecto de investigaciónes
unq.versioninfo:eu-repo/semantics/publishedVersionen
unq.proyecto.tipoPUNQ I+D (Proyecto)es
unq.proyecto.inicio2015-05-01
unq.proyecto.final2017-04-30
unq.proyecto.estadoEn cursoes
unq.proyecto.directorSoulignac, Francisco
unq.proyecto.integranteFactorovich, Pablo
unq.proyecto.integranteDelgadillo Cárdenas, Remberto Emanuel
unq.proyecto.integranteTerlisky, Pablo
unq.proyecto.integranteBonelli, Eduardo
unq.proyecto.integranteLaime, Jesús
unq.proyecto.integranteLeutwyler, Nicolás
unq.proyecto.integranteSandoval, Lucas
unq.departamentoDepartamento de Ciencia y Tecnologíaes
unq.tipo.snrdinfo:eu-repo/semantics/otheren
unq.accesoinfo:eu-repo/semantics/openAccessen
unq.proyecto.areaCiencias de la Computaciónes
unq.proyecto.resumenEl objetivo central del proyecto es diseñar algoritmos eficientes para problemas de grafos, previo estudio de su tratabilidad. Nos centramos, en particular, en los problemas de coloreo y transversal en hipergrafos de intersección y en el problema de diseño de redes. Asimismo, estudiamos distintas clases de grafos, enfocándonos en los problemas de reconocimiento, certificación y representación. El objetivo es poder estudiar los problemas combinatorios sobre las clases estudiadas, aprovechando sus particularidades. Para el diseño de los algoritmos, utilizamos distintos enfoques metodológicos. Cuando el problema en cuestión es tratable, proponemos desarrollar algoritmos con una complejidad asintótica menor a la conocida actualmente. Para ello, estudiamos las propiedades estructurales de los grafos considerados que permiten hacer un uso eficiente de los recursos, y diseñamos algoritmos y estructuras de datos específicas para estos problemas. Cuando el problema es intratable, el objetivo es diseñar algoritmos eficientes que brinden mejores soluciones a las ya conocidas en un tiempo comparable. En este proyecto consideramos dos técnicas conocidas para los problemas intratables. La primera es el uso de metaheurísticas que exploren inteligentemente el espacio de soluciones factibles. La dificultad de diseñar un algoritmo metaheuristico está en decidir cómo se explora el espacio, y cómo se implementa eficientemente cada algoritmo que lo compone. La segunda es la aplicación de algoritmos del estilo branch-and-bound (branch-and-cut, branch-and-price, etc), en las que se inspecciona un árbol de búsqueda. La dificultad en este caso está en cómo resolver cada nodo del árbol (aplicando heurísticas y relajaciones lineales) y en decidir el orden en el que se procesan los mismos a fin de acotar el espacio de búsqueda usando la menor cantidad de tiempo posible. Esta técnica requiere la formulación de un modelo de programación lineal entera que define el espacio de búsqueda. Finalmente, también consideramos la tratabilidad de los problemas en cuestión, que es un paso previo necesario para determinar qué técnica conviene aplicar para resolver un problema. Además del avance en el estado del arte en los problemas estudiados, esperamos conformar un grupo de estudio de temas de investigación operativa, particularmente en el estudio de algoritmos en grafos. Esperamos una repercusión positiva en la formación de los alumnos de grado de la incipiente Licenciatura en Desarrollo de Software en un tema particularmente útil para el sector productivo.es


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record