Mostrar el registro sencillo del ítem
Problema de la secretaria simple y matroidal con consejos ordinales
Profesor guía | dc.contributor.advisor | Soto San Martín, José | |
Autor | dc.contributor.author | Valdevenito Werner, Felipe Andrés | |
Profesor colaborador | dc.contributor.other | Kiwi Krauskopf, Marcos | |
Profesor colaborador | dc.contributor.other | Verdugo Silva, Víctor | |
Fecha ingreso | dc.date.accessioned | 2024-04-30T21:04:39Z | |
Fecha disponible | dc.date.available | 2024-04-30T21:04:39Z | |
Fecha de publicación | dc.date.issued | 2023 | |
Identificador | dc.identifier.other | 10.58011/xmgc-qr44 | |
Identificador | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/198349 | |
Resumen | dc.description.abstract | Examinamos variaciones del Problema de la Secretaria Simple (con una sola selecci´on) y del Problema de la Secretaria Matroidal en un nuevo escenario, en el cual el tomador de decisiones (el jugador) puede solicitar uno (o m´as) bits de informaci´on ordinal de los candidatos antes de que lleguen. Espec´ıficamente, cada candidato tiene informaci´on privada (su “peso”) que es revelada al momento que el candidato llega. Como es usual, el jugador debe decidir irrevocablemente si seleccionar al candidato o no despu´es de este paso. Adicionalmente, consideramos modelos en los que el jugador puede realizar preguntas ordinales binarias a los candidatos que a´un no han llegado, y los candidatos pueden responder bas´andose solo en su propia informaci´on privada m´as la informaci´on p´ublicamente disponible hasta el momento. Llamamos a esta informaci´on adicional consejo ordinal. Por ejemplo, el jugador puede preguntar a cada candidato que a´un no llega si su peso oculto es mayor que todos los pesos de candidatos que ya han llegado, pero no le puede preguntar si su peso es el mayor de la lista completa. En la versi´on del problema con ´unica selecci´on, el objetivo es seleccionar al candidato de mayor peso de la lista. Consideramos diferentes maneras en que los candidatos llegan, tales como en orden aleatorio, en orden adversarial, o con una muestra aleatoria de candidatos que se revelan de antemano. En el ´ultimo caso, el jugador decide la cantidad de candidatos incluidos en la muestra, y el resto de los candidatos llegan en un orden elegido por un adversario ya sea antes o despu´es de la realizaci´on de la muestra. Exploramos el impacto de variar la cantidad de consejos ordinales que se pueden solicitar, considerando los casos en que se puede consultar cero, una o ilimitadas veces. Presentamos algoritmos que alcanzan competitividades ´optimas para casi todos los escenarios considerados. Finalmente, investigamos la versi´on matroidal del problema, en la cual los candidatos son elementos de una matroide conocida, y el jugador solo puede seleccionar elementos incrementalmente tal que se forme un conjunto independiente de la matroide. Notablemente, probamos que incluso una sola ronda de consejos ordinales es suficiente para alcanzar competitividades constantes (independientes del rango de la matroide) si se dispone de una muestra aleatoria. Tambi´en presentamos algoritmos con competitividades ´optimas para varios de los escenarios presentados. | es_ES |
Patrocinador | dc.description.sponsorship | CMM ANID BASAL FB210005, FONDECYT REGULAR 1181180 y FONDECYT REGULAR 1231669 | es_ES |
Idioma | dc.language.iso | es | es_ES |
Publicador | dc.publisher | Universidad de Chile | es_ES |
Tipo de licencia | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
Link a Licencia | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
Título | dc.title | Problema de la secretaria simple y matroidal con consejos ordinales | es_ES |
Tipo de documento | dc.type | Tesis | es_ES |
dc.description.version | dc.description.version | Versión original del autor | es_ES |
dcterms.accessRights | dcterms.accessRights | Acceso abierto | es_ES |
Catalogador | uchile.catalogador | gmm | es_ES |
Departamento | uchile.departamento | Departamento de Ingeniería Matemática | es_ES |
Facultad | uchile.facultad | Facultad de Ciencias Físicas y Matemáticas | es_ES |
uchile.titulacion | uchile.titulacion | Doble Titulación | es_ES |
uchile.carrera | uchile.carrera | Ingeniería Civil Matemática | es_ES |
uchile.gradoacademico | uchile.gradoacademico | Magister | es_ES |
uchile.notadetesis | uchile.notadetesis | Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas | es_ES |
uchile.notadetesis | uchile.notadetesis | Memoria para optar al título de Ingeniero Civil Matemático |
Descargar archivo
Este ítem aparece en la(s) siguiente(s) colección(ones)
-
Tesis Postgrado
Tesis Postgrado