{"id":86412,"date":"2018-03-10T00:10:58","date_gmt":"2018-03-10T00:10:58","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/algoritmos-para-problemas-de-optimizacion-bajo-total-monotonia\/"},"modified":"2018-03-10T00:10:58","modified_gmt":"2018-03-10T00:10:58","slug":"algoritmos-para-problemas-de-optimizacion-bajo-total-monotonia","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/algoritmos-para-problemas-de-optimizacion-bajo-total-monotonia\/","title":{"rendered":"Algoritmos para problemas de optimizaci\u00f3n bajo total monotonia"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Pedro Jodra Esteban <\/strong><\/h2>\n<p>En esta memoria se desarrollan algoritmos on-line para buscar m\u00ednimos en matrices multidimensionales bajo la propiedad de total monotonia. Este tipo de cuestiones aparecen de una forma natural al formular problemas de recorridos en el plano utilizando las t\u00e9cnicas de programaci\u00f3n din\u00e1mica.  en primer lugar, se dise\u00f1a un algoritmo lineal de busqueda de m\u00ednimos en m\u00e1trices monge path-de composable tridimensionales. Este algoritmo permite resolver de forma \u00f3ptima tres problemas de optimizaci\u00f3n bien conocidos en la literatura: el problema de la curva kamiltoniana de longitud unina con extremos fijos en un onvexo. El problema del viajante de comercio para puntos sobre un convexo y una recta en su interior, y el problema de m\u00ednima latencia en grafos camino.  a continuaci\u00f3n, el algoritmo dado se generaliza para b\u00fasqueda on-line de m\u00ednimos en matrices monge path-recompensable de mayor dimensi\u00f3n. Adem\u00e1s, dise\u00f1amos un algoritmo on-line para matrices multidimensionales que satisfacen la propiedad monge en lugar de la monge path-decomposable.  por otra parte, para matrices antimonge path-decomposable tridimensionales damos un algoritmo de complejidad o(nlogn) en tiempo 1 lineal en espacio . Este algoritmo permite resolver de manera m\u00e1s efecientemente que la conocida el problema de la curva hamiltoniana m\u00ednima con extremos arbitrarios, tanto en un poligono convexo como en uno simple.  finalmente, damos un algoritmo \u00f3ptimo para el problema del viajante de comercio con deaolines en un grafio camino.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Algoritmos para problemas de optimizaci\u00f3n bajo total monotonia<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Algoritmos para problemas de optimizaci\u00f3n bajo total monotonia <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Pedro Jodra Esteban <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Zaragoza<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 18\/09\/2000<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Alfredo Garcia Olaverri<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Luis Coladas uria <\/li>\n<li>herminia Salvete fern\u00e1ndez (vocal)<\/li>\n<li>joaqu\u00edn Sicilia rodriguez (vocal)<\/li>\n<li>ferran Huratado d\u00edaz (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Pedro Jodra Esteban En esta memoria se desarrollan algoritmos on-line para buscar m\u00ednimos en matrices multidimensionales bajo [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[6264,126,37086,13610],"tags":[105652,181417,181416,28881,35185,181415],"class_list":["post-86412","post","type-post","status-publish","format-standard","hentry","category-investigacion-operativa","category-matematicas","category-programacion-dinamica","category-zaragoza","tag-alfredo-garcia-olaverri","tag-ferran-huratado-diaz","tag-herminia-salvete-fernandez","tag-joaquin-sicilia-rodriguez","tag-luis-coladas-uria","tag-pedro-jodra-esteban"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/86412","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=86412"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/86412\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=86412"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=86412"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=86412"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}