Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
"Max cut es el problema de hallar el corte máximo sobre los vértices de un grafo en el cual se le ha asignado un valor no negativo y racional a cada arista. Este problema es NP-Hard y por tanto no existe un algoritmo que lo resuelva en tiempo polinomial a menos que P = NP. Goemans y Williamson...
- Autores:
-
Corpus Vanegas, Eugenio Miguel
- Tipo de recurso:
- Fecha de publicación:
- 2016
- Institución:
- Universidad de los Andes
- Repositorio:
- Séneca: repositorio Uniandes
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.uniandes.edu.co:1992/13277
- Acceso en línea:
- http://hdl.handle.net/1992/13277
- Palabra clave:
- Teoría de grafos - Investigaciones
Análisis combinatorio - Investigaciones
Matemáticas
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by-nc-sa/4.0/
| Summary: | "Max cut es el problema de hallar el corte máximo sobre los vértices de un grafo en el cual se le ha asignado un valor no negativo y racional a cada arista. Este problema es NP-Hard y por tanto no existe un algoritmo que lo resuelva en tiempo polinomial a menos que P = NP. Goemans y Williamson diseñaron un m-algoritmo de aproximación aleatorio para max cut con m=0,87856... al cual en este trabajo llamaremos algoritmo G-W, este aprovecha la equivalencia de max cut con el problema de programación entera..." |
|---|