Mostrar el registro sencillo del ítem
Un problema de barrido de calles
Colaborador: | CHAVEZ LOMELI, LAURA ELENA |
Colaborador: | ZARAGOZA MARTINEZ, FRANCISCO JAVIER |
Autor: | HERNANDEZ SANCHEZ, LUIS FRANCISCO |
Fecha de publicación: | 2015-02-11 |
URI: | http://hdl.handle.net/11191/5738 |
Descripción: | 76 páginas. Maestría en Optimización. |
Resumen: | El problema de barrido de calles, en inglés Street Sweeping Problem (SSP) es una variante del problema del cartero con viento, en inglés el Windy Postman Problem (WPP), en el cual se deben construir dos recorridos que pasen por cada calle por lo menos una vez en cada dirección, barriendo una dirección en el primer recorrido y la otra dirección en el segundo recorrido. Se estudió el SSP junto con algunas variantes. Se presentó un modelo de programación entera del problema y se consideraron los poliedros definidos por la relajación de programación lineal del problema original. Se descrubrió algunas características de los poliedros asociados en el caso general. También se estudiaron los poliedros asociados a casos particulares de gráficas y sus características. Posteriormente se diseñó e implementó un algoritmo de aproximación para el SSP con garantía 3/2 α + 1 para cualquier gráfica, utilizando como subrutina algún algoritmo de aproximación para el WPP con garantía α. Después se presentó otro algoritmo de aproximación que mejora los algoritmos previos y da una garantía 2 para cualquier clase de gráfica con un tiempo polinomial de ejecución. Además se presentaron algoritmos exactos para algunas clases de gráficas. La complejidad computacional de este problema permanece abierta. |
Formato: | |
Idioma: | spa |
Editor: | Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. Coordinación de Servicios de Información. |
Palabras clave: | Street Sweeping Problem (SSP); Algoritmos de aproximación. |
Materias: | CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA::MATEMÁTICAS::CIENCIA DE LOS ORDENADORES::LENGUAJES ALGORÍTMICOS |
Clasificación LC: | TD813 |
Materias: | Street cleaning. |
Materias: | Limpieza de las calles. |
Materias: | Programación entera. |
Materias: | Optimización matemática. |
Título: | Un problema de barrido de calles |
Tipo de publicación: | Tesis de maestría |
Audiencia: | students |
Audiencia: | researchers |
División: | División de Ciencias Básicas e Ingeniería. |
Nivel del grado: | Maestría. |
Otorgante del grado: | Universidad Autónoma Metropolitana (México). Unidad Azcapotzalco. |
Nombre del Grado: | Maestría en Optimización. |
Origen del formato: | Born digital |