Registro:
| Documento: | Tesis de Grado |
| Título: | Un estudio poliedral del problema de coloreo de maximo impacto en hipergrafos |
| Autor: | Singer, Jessica |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2023 |
| Fecha en portada: | 2023 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Marenco, Javier Leonardo |
| Jurado: | Méndez Díaz, Isabel; Zabala, Paula Lorena |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000541_Singer |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000541_Singer.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000541_Singer |
| Ubicación: | Dep.COM 000541 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Singer, Jessica. (2023). Un estudio poliedral del problema de coloreo de maximo impacto en hipergrafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000541_Singer |
Resumen:
Dados un grafo G = (V, E), un hipergrafo H = (V, EH) sobre el mismo conjunto de vértices y un conjunto C de colores, el problema de coloreo de máximo impacto en hipergrafos consiste en hallar un coloreo factible, es decir, una función c : V → C con c(i) ̸= c(j) para toda arista ij ∈ E(G), tal que se maximice la cantidad de hiper aristas de H que se asignan al mismo color. Este problema surge en el contexto de asignación de aulas a clases, donde V es el conjunto de clases semanales de una institución educativa, C son las aulas de la misma, y las aristas del grafo H conectan a las clases de una misma asignatura. En este sentido, una particularidad que intentaremos modelar será la preferencia por asignar a todas las clases de una misma asignatura, una misma aula. Sin embargo, habrá que tomar en cuenta los casos donde esto no será posible por superposiciones horarias. Para este problema, analizamos dos modelos basados en programación lineal entera, concluyendo que uno de ellos muestra una ejecución más veloz en la práctica. Utilizando el modelo ganador, hacemos un estudio del poliedro inducido por las soluciones factibles de este, calculando su dimensión y buscando desigualdades válidas y facetas.
Citación:
---------- APA ----------
Singer, Jessica. (2023). Un estudio poliedral del problema de coloreo de maximo impacto en hipergrafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000541_Singer
---------- CHICAGO ----------
Singer, Jessica. "Un estudio poliedral del problema de coloreo de maximo impacto en hipergrafos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2023.https://hdl.handle.net/20.500.12110/seminario_nCOM000541_Singer
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000541_Singer.pdf
Distrubución geográfica
