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

Full description

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
Acceso en línea:
http://hdl.handle.net/10554/59479
https://doi.org/10.11144/Javeriana.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
id JAVERIANA_bfadfc11ce6a8d2696d6c8cd7abf7cee
oai_identifier_str oai:repository.javeriana.edu.co:10554/59479
network_acronym_str JAVERIANA
network_name_str Repositorio Universidad Javeriana
repository_id_str
dc.title.none.fl_str_mv Submodularity and combinatorial representations for the multicommodity network design problem
Submodularity and combinatorial representations for the multicommodity network design problem
title Submodularity and combinatorial representations for the multicommodity network design problem
spellingShingle Submodularity and combinatorial representations for the multicommodity network design problem
Gutierrez Diaz, Diana Carolina
Network design
Network design
Maestría en matemáticas - Tesis y disertaciones académicas
Algoritmos heurísticos
Redes (Circuitos)
title_short Submodularity and combinatorial representations for the multicommodity network design problem
title_full Submodularity and combinatorial representations for the multicommodity network design problem
title_fullStr Submodularity and combinatorial representations for the multicommodity network design problem
title_full_unstemmed Submodularity and combinatorial representations for the multicommodity network design problem
title_sort Submodularity and combinatorial representations for the multicommodity network design problem
dc.creator.none.fl_str_mv Gutierrez Diaz, Diana Carolina
author Gutierrez Diaz, Diana Carolina
author_facet Gutierrez Diaz, Diana Carolina
author_role author
dc.contributor.none.fl_str_mv Ortiz Astorquiza, Camilo
Contreras, Ivan
dc.subject.none.fl_str_mv Network design
Network design
Maestría en matemáticas - Tesis y disertaciones académicas
Algoritmos heurísticos
Redes (Circuitos)
topic Network design
Network design
Maestría en matemáticas - Tesis y disertaciones académicas
Algoritmos heurísticos
Redes (Circuitos)
description 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.
publishDate 2022
dc.date.none.fl_str_mv 2022-04-08T14:55:22Z
2022-04-08T14:55:22Z
2022-03-25
dc.type.none.fl_str_mv http://purl.org/coar/version/c_ab4af688f83e57aa
Tesis/Trabajo de grado - Monografía - Maestría
http://purl.org/coar/resource_type/c_bdcc
info:eu-repo/semantics/masterThesis
info:eu-repo/semantics/publishedVersion
format masterThesis
status_str publishedVersion
dc.identifier.none.fl_str_mv http://hdl.handle.net/10554/59479
https://doi.org/10.11144/Javeriana.10554.59479
instname:Pontificia Universidad Javeriana
reponame:Repositorio Institucional - Pontificia Universidad Javeriana
repourl:https://repository.javeriana.edu.co
url http://hdl.handle.net/10554/59479
https://doi.org/10.11144/Javeriana.10554.59479
identifier_str_mv instname:Pontificia Universidad Javeriana
reponame:Repositorio Institucional - Pontificia Universidad Javeriana
repourl:https://repository.javeriana.edu.co
dc.language.none.fl_str_mv spa
language spa
dc.rights.none.fl_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
http://creativecommons.org/licenses/by-nc-nd/4.0/
info:eu-repo/semantics/embargoedAccess
http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
http://creativecommons.org/licenses/by-nc-nd/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv embargoedAccess
dc.format.none.fl_str_mv PDF
application/pdf
application/pdf
application/pdf
dc.publisher.none.fl_str_mv Pontificia Universidad Javeriana
Maestría en Matemáticas
Facultad de Ciencias
publisher.none.fl_str_mv Pontificia Universidad Javeriana
Maestría en Matemáticas
Facultad de Ciencias
dc.source.none.fl_str_mv reponame:Repositorio Universidad Javeriana
instname:Pontificia Universidad Javeriana
instacron:Pontificia Universidad Javeriana
instname_str Pontificia Universidad Javeriana
instacron_str Pontificia Universidad Javeriana
institution Pontificia Universidad Javeriana
reponame_str Repositorio Universidad Javeriana
collection Repositorio Universidad Javeriana
_version_ 1803712809434873856
spelling Submodularity and combinatorial representations for the multicommodity network design problemSubmodularity and combinatorial representations for the multicommodity network design problemGutierrez Diaz, Diana CarolinaNetwork designNetwork designMaestría en matemáticas - Tesis y disertaciones académicasAlgoritmos heurísticosRedes (Circuitos)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.We present a new combinatorial representation for the multicommodity network design problem (MUND), such that its objective function satisfies the submodularity property. Thanks to the submodularity property it is possible to establish heuristics, for two variants of the problem, such that their heuristics are approximation algorithms that run in polynomial time and for which it is possible to set worst-case bounds of 1/e for large instances.Magíster en MatemáticasMaestríahttps://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0001829729Pontificia Universidad JaverianaMaestría en MatemáticasFacultad de CienciasOrtiz Astorquiza, CamiloContreras, Ivan2022-04-08T14:55:22Z2022-04-08T14:55:22Z2022-03-25http://purl.org/coar/version/c_ab4af688f83e57aaTesis/Trabajo de grado - Monografía - Maestríahttp://purl.org/coar/resource_type/c_bdccinfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/publishedVersionPDFapplication/pdfapplication/pdfapplication/pdfhttp://hdl.handle.net/10554/59479https://doi.org/10.11144/Javeriana.10554.59479instname:Pontificia Universidad Javerianareponame:Repositorio Institucional - Pontificia Universidad Javerianarepourl:https://repository.javeriana.edu.cospaAtribución-NoComercial-SinDerivadas 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/embargoedAccessDe acuerdo con la naturaleza del uso concedido, la presente licencia parcial se otorga a título gratuito por el máximo tiempo legal colombiano, con el propósito de que en dicho lapso mi (nuestra) obra sea explotada en las condiciones aquí estipuladas y para los fines indicados, respetando siempre la titularidad de los derechos patrimoniales y morales correspondientes, de acuerdo con los usos honrados, de manera proporcional y justificada a la finalidad perseguida, sin ánimo de lucro ni de comercialización. De manera complementaria, garantizo (garantizamos) en mi (nuestra) calidad de estudiante (s) y por ende autor (es) exclusivo (s), que la Tesis o Trabajo de Grado en cuestión, es producto de mi (nuestra) plena autoría, de mi (nuestro) esfuerzo personal intelectual, como consecuencia de mi (nuestra) creación original particular y, por tanto, soy (somos) el (los) único (s) titular (es) de la misma. Además, aseguro (aseguramos) que no contiene citas, ni transcripciones de otras obras protegidas, por fuera de los límites autorizados por la ley, según los usos honrados, y en proporción a los fines previstos; ni tampoco contempla declaraciones difamatorias contra terceros; respetando el derecho a la imagen, intimidad, buen nombre y demás derechos constitucionales. Adicionalmente, manifiesto (manifestamos) que no se incluyeron expresiones contrarias al orden público ni a las buenas costumbres. En consecuencia, la responsabilidad directa en la elaboración, presentación, investigación y, en general, contenidos de la Tesis o Trabajo de Grado es de mí (nuestro) competencia exclusiva, eximiendo de toda responsabilidad a la Pontifica Universidad Javeriana por tales aspectos. Sin perjuicio de los usos y atribuciones otorgadas en virtud de este documento, continuaré (continuaremos) conservando los correspondientes derechos patrimoniales sin modificación o restricción alguna, puesto que, de acuerdo con la legislación colombiana aplicable, el presente es un acuerdo jurídico que en ningún caso conlleva la enajenación de los derechos patrimoniales derivados del régimen del Derecho de Autor. De conformidad con lo establecido en el artículo 30 de la Ley 23 de 1982 y el artículo 11 de la Decisión Andina 351 de 1993, "Los derechos morales sobre el trabajo son propiedad de los autores", los cuales son irrenunciables, imprescriptibles, inembargables e inalienables. En consecuencia, la Pontificia Universidad Javeriana está en la obligación de RESPETARLOS Y HACERLOS RESPETAR, para lo cual tomará las medidas correspondientes para garantizar su observancia.http://purl.org/coar/access_right/c_abf2reponame:Repositorio Universidad Javerianainstname:Pontificia Universidad Javerianainstacron:Pontificia Universidad Javeriana2023-04-30T05:00:00Z

Publicaciones similares