Submodularity and combinatorial representations for the multicommodity network design problem
Presentamos una nueva representación combinatoria para el problema de diseño de redes multiproducto (MUND), tal que su función objetivo satisface la propiedad de submodularidad. Gracias a la propiedad de submodularidad es posible establecer heurísticas, para dos variantes del problema, tales que dic...
- Autores:
- Tipo de recurso:
- masterThesis
- Fecha de publicación:
- 2022
- Institución:
- Pontificia Universidad Javeriana
- Repositorio:
- Repositorio Universidad Javeriana
- Idioma:
- spa
- OAI Identifier:
- oai:repository.javeriana.edu.co:10554/59479
- Palabra clave:
- Network design
Network design
Maestría en matemáticas - Tesis y disertaciones académicas
Algoritmos heurísticos
Redes (Circuitos)
- Rights
- embargoedAccess
- License
- Atribución-NoComercial-SinDerivadas 4.0 Internacional
| Summary: | Presentamos una nueva representación combinatoria para el problema de diseño de redes multiproducto (MUND), tal que su función objetivo satisface la propiedad de submodularidad. Gracias a la propiedad de submodularidad es posible establecer heurísticas, para dos variantes del problema, tales que dichas heurísticas sean algoritmos de aproximación que corren en tiempo polinomial y para los cuales es posible establecer cotas del peor caso de 1/e para grandes instancias. |
|---|