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 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.

Grantor dc:publisher

Pontificia Universidad Javeriana

Author dc:creator

• Gutierrez Diaz, Diana Carolina

Advisors dc:contributor.advisor

• Ortiz Astorquiza, Camilo
• Contreras, Ivan

• Network design

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

spa

DOI

https://doi.org/10.11144/Javeriana.10554.59479

OAI record oai:identifier

https://repository.javeriana.edu.co/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Arepository.javeriana.edu.co%3A10554%2F59479