Browsing by Author "Soto San Martín, José"
Now showing items 21-40 of 41
-
(Universidad de Chile, 2016)El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N candidatos a un puesto de secretaria para ...
-
(SIAM, 2015)Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger ...
-
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity (Springer, 2015)Given a set of n axis-parallel rectangles in the plane, finding a maximum independent set (MIS), amaximumweighted independent set (WMIS), and aminimum hitting set (MHS), are basic problems in computational geometry and ...
-
(Universidad de Chile, 2014)En la presente memoria se considera la relación entre coloreamiento de vértices y la noción de inmersión. Específicamente, se estudia una conjetura propuesta por Abu-Khzam y Langston, la cual dice que el grafo completo ...
-
(Cambridge University Press, 2015)To Philippe Flajolet, a mathematical discontinuity, a tamer of singularities. A two-row array of integers an = a1 a2 ... an b1 b2 ... bn is said to be in lexicographic order if its columns are in lexicographic order (where ...
-
(Springer, 2019)We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to ...
-
(2013)The matroid secretary problem admits several variants according to the order in which the matroid’s elements are presented and how the elements are assigned weights. As the main result of this article, we devise the first ...
-
(Universidad de Chile, 2023)Al momento de resolver el problema de ruteo de vehículos en ciertos contextos prácticos se vuelve deseable tener cierta noción de zonificación del problema, además existen estrategias que están basadas en realizar una ...
-
(Universidad de Chile, 2019)Dado un conjunto finito de N vértices, el tiempo de viaje entre cada uno de ellos, una cantidad m de vehículos y un punto de origen llamado depósito, en el multiple traveling salesman problem se desea encontrar m rutas ...
-
(Universidad de Chile, 2017)Estudiamos una generalización del problema de la secretaria llamada el problema matroidal de la secretaria propuesta en 2007 por Babaioff et al. [1]. En este problema, los elementos de una matroide se revelan en orden ...
-
(Universidad de Chile, 2022)El problema de Optimizaci\'on de Ganancias C\'oncavas en M\'aquinas Paralelas consiste en, dados conjuntos $J$ de trabajos, $I$ de m\'aquinas que pueden procesar dichos trabajos y $\{f_j\}_{j \in J}$ de funciones de ganancias ...
-
(Universidad de Chile, 2020)El problema que motivó este trabajo, llamado problema del Traslado de Personal Ope- rativo (TPO), es la planificación de rutas e itinerarios de vehículos que, en conjunto con la utilización de una red de transporte de ...
-
(Universidad de Chile, 2013)La presente memoria tiene como objetivo el estudio del problema de reconstrucción de redes en sistemas distribuidos que utilizan mensajes pequeños. Esto resulta de gran interés en la actualidad debido a la existencia de ...
-
(Universidad de Chile, 2022)El presente trabajo estudia un problema de asignación de clientes a centros de atención: dado un conjunto de clientes en un grafo métrico, y un conjunto de centros en los cuales hay servidores disponibles, se desea asignar ...
-
(Universidad de Chile, 2012)Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso ...
-
(Universidad de Chile, 2017)El objetivo de este trabajo es estudiar el problema de asignación escolar como uno de asignación probabilística y poder entender como diversos mecanismos de asignación escolar se desempeñan en términos de las probabilidades ...
-
(Universidad de Chile, 2021)Los mecanismos centralizados para la asignación de estudiantes a establecimientos educacionales han recibido creciente atención durante las últimas décadas. Desde las populares aplicaciones del Algoritmo de Aceptación ...
-
(Universidad de Chile, 2020)El problema de la secretaria o el juego de Googol son modelos clásicos para problemas de selección en línea que han recibido atención significativa en las últimas cinco décadas. En este trabajo consideramos una variante ...
-
(Universidad de Chile, 2021)En esta tesis se estudia una serie de problemas en combinatoria extremal y probabilista relacionados a árboles y palabras. En la primera parte de este trabajo se estudian qué condiciones debe cumplir un grafo para que ...
-
(Universidad de Chile, 2018)En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, ...
