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

Full description

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/
id UNIANDES2_4fd61071e28feacd4a9ce874a9377384
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/13277
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
spelling Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.http://creativecommons.org/licenses/by-nc-sa/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Velasco Gregory, Mauricio Fernando7444a9c4-bd1b-4d73-9cce-a9276e474d20500Corpus Vanegas, Eugenio Miguel24d8db41-7fe1-4c18-b835-64e84588a3ab500Junca Peláez, Mauricio JoséMeziat Vélez, René Joaquín2018-09-28T10:32:05Z2018-09-28T10:32:05Z2016http://hdl.handle.net/1992/13277u721822.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/"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..."Magíster en MatemáticasMaestría35 hojasapplication/pdfspaUniandesMaestría en MatemáticasFacultad de CienciasDepartamento de Matemáticasinstname:Universidad de los Andesreponame:Repositorio Institucional SénecaAproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorioTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesishttp://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/TMTeoría de grafos - InvestigacionesAnálisis combinatorio - InvestigacionesMatemáticasPublicationTEXTu721822.pdf.txtu721822.pdf.txtExtracted texttext/plain83117https://repositorio.uniandes.edu.co/bitstreams/23bf287a-b78c-4b8d-8d81-ab80bd3ecafc/download9f3f59cf3fe68617f711811aa30f875fMD54ORIGINALu721822.pdfapplication/pdf428377https://repositorio.uniandes.edu.co/bitstreams/101e590e-c6a8-44f1-a5bc-8a9611141d09/download92c881f29939eba8be2e8287067b8b8fMD51THUMBNAILu721822.pdf.jpgu721822.pdf.jpgIM Thumbnailimage/jpeg15291https://repositorio.uniandes.edu.co/bitstreams/943e94ce-f71a-42f7-941e-8d96ffa28187/downloadd9be450891bd1d1184dfada31b948c86MD551992/13277oai:repositorio.uniandes.edu.co:1992/132772023-10-10 18:15:23.189http://creativecommons.org/licenses/by-nc-sa/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co
dc.title.es_CO.fl_str_mv Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
title Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
spellingShingle Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
Teoría de grafos - Investigaciones
Análisis combinatorio - Investigaciones
Matemáticas
title_short Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
title_full Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
title_fullStr Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
title_full_unstemmed Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
title_sort Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio
dc.creator.fl_str_mv Corpus Vanegas, Eugenio Miguel
dc.contributor.advisor.none.fl_str_mv Velasco Gregory, Mauricio Fernando
dc.contributor.author.none.fl_str_mv Corpus Vanegas, Eugenio Miguel
dc.contributor.jury.none.fl_str_mv Junca Peláez, Mauricio José
Meziat Vélez, René Joaquín
dc.subject.keyword.es_CO.fl_str_mv Teoría de grafos - Investigaciones
Análisis combinatorio - Investigaciones
topic Teoría de grafos - Investigaciones
Análisis combinatorio - Investigaciones
Matemáticas
dc.subject.themes.none.fl_str_mv Matemáticas
description "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..."
publishDate 2016
dc.date.issued.none.fl_str_mv 2016
dc.date.accessioned.none.fl_str_mv 2018-09-28T10:32:05Z
dc.date.available.none.fl_str_mv 2018-09-28T10:32:05Z
dc.type.spa.fl_str_mv Trabajo de grado - Maestría
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TM
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/1992/13277
dc.identifier.pdf.none.fl_str_mv u721822.pdf
dc.identifier.instname.spa.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.spa.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url http://hdl.handle.net/1992/13277
identifier_str_mv u721822.pdf
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.es_CO.fl_str_mv spa
language spa
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.es_CO.fl_str_mv 35 hojas
dc.format.mimetype.es_CO.fl_str_mv application/pdf
dc.publisher.es_CO.fl_str_mv Uniandes
dc.publisher.program.es_CO.fl_str_mv Maestría en Matemáticas
dc.publisher.faculty.es_CO.fl_str_mv Facultad de Ciencias
dc.publisher.department.es_CO.fl_str_mv Departamento de Matemáticas
dc.source.es_CO.fl_str_mv instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
instname_str Universidad de los Andes
institution Universidad de los Andes
reponame_str Repositorio Institucional Séneca
collection Repositorio Institucional Séneca
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/23bf287a-b78c-4b8d-8d81-ab80bd3ecafc/download
https://repositorio.uniandes.edu.co/bitstreams/101e590e-c6a8-44f1-a5bc-8a9611141d09/download
https://repositorio.uniandes.edu.co/bitstreams/943e94ce-f71a-42f7-941e-8d96ffa28187/download
bitstream.checksum.fl_str_mv 9f3f59cf3fe68617f711811aa30f875f
92c881f29939eba8be2e8287067b8b8f
d9be450891bd1d1184dfada31b948c86
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1812133983719260160

Publicaciones similares