Browsing by Author "Soto San Martín, José"
Now showing items 1-20 of 47
-
(Universidad de Chile, 2019)El k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases de grafos, para intentar resolverlo en ...
-
A hierarchy between distributed communication models combining broadcast, congest and local rounds (Universidad de Chile, 2022)En esta tesis, enmarcada en computación distribuida, se estudian diferentes modelos de comunicación distribuida construidos a partir de la combinación de rondas de modelos pre- existentes tales como broadcast, congest y ...
-
(SIAM publications, 2013)We present an efficient algorithm to find nonempty minimizers of a symmetric submodular function f over any family of sets I closed under inclusion. Our algorithm makes O(n(3)) oracle calls to f and I, where n is the ...
-
(Universidad de Chile, 2023)El problema clásico de la secretaria introdujo una plétora de generalizaciones. En esta tesis se estudia la versión donde tenemos una sola muestra de las distribuciones de cada valor, en el caso particular donde los ...
-
(Universidad de Chile, 2021)En las formulaciones matemáticas más conocidas de los problemas de ruteo de vehículos es asumido que todos los clientes son conocidos desde un principio, permitiendo construir soluciones planificadas. Sin embargo, en ...
-
(Universidad de Chile, 2021)Los problemas de aumentación de conectividad son un caso particular del Survivable Network Problem, que ha sido muy estudiado en las últimas décadas por sus aplicaciones en el diseño de redes robustas. Estos problemas ...
-
(Universidad de Chile, 2014)En este trabajo se estudian problemas de programación de tareas en un entorno de máquinas paralelas. A diferencia de la literatura clásica, asumimos que los trabajos pueden ser divididos en distintas partes, cada una de ...
-
(Universidad de Chile, 2024)En el área de algoritmos combinatoriales de optimización, los problemas de agendamiento buscan asignaciones de trabajos a máquinas. La carga de una máquina es la suma de los tiempos de proceso de sus trabajos asignados. En ...
-
Algoritmos distribuidos en clases de grafos y un nuevo modelo dinámico de verificación distribuida (Universidad de Chile, 2022)Esta tesis consta de dos partes. En la primera se estudia el problema del cálculo del diámetro en diferentes modelos de computación distribuida. Se inicia por describir un Proof Labeling Scheme (PLS) para resolver el ...
-
(Universidad de Chile, 2015)En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina ...
-
(Universidad de Chile, 2020)En esta memoria se enfrentan dos problemas. El primero de ellos es Unsplittable Flow on Trees, en el cual dados un árbol con capacidades G, un conjunto de flujos de distintos tamaños T' y un natural k, se busca encontrar ...
-
(Universidad de Chile, 2021)El problema de minimizar k-sum lateness en una máquina es una generalización de los problemas de minimizar maximum lateness y total lateness, casos que se recuperan cuando k=1 y k=n respectivamente, y consiste en encontrar ...
-
(Universidad de Chile, 2018)Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e ...
-
(ACADEMIC PRESS, 2008-07)We say that a square matrix M of order r is a degree matrix of a given graph G if there is a so-called equitable partition of its vertices into r blocks with the following property: For any i and j it holds that a vertex ...
-
(Universidad de Chile, 2021)En un digrafo, una bubble se define como un par de caminos dirigidos con vértices extremos comunes, pero internamente disjuntos. Aparecen naturalmente en el grafo de ensamblaje generado con el fin de realizar la secuenciación ...
-
(Universidad de Chile, 2014)La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, ...
-
(Universidad de Chile, 2017)En esta tesis se estudia el desarrollo de cuestionarios eficientes para el modelo de elección discreta de eliminación por aspectos. El estudio está motivado por la teoría de error desarrollada por Kohli, Jedidi y Montoya ...
-
(Universidad de Chile, 2013)La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz ...
-
(Universidad de Chile, 2018)En este trabajo se estudian dos preguntas surgidas durante la implementación del Sistema de Admisión Escolar chileno, el cual asigna de manera centralizada estudiantes a colegios según sus preferencias, usando el algoritmo ...
-
(Universidad de Chile, 2014)Se estudia la estructura de grafos completos de tamaño apropiado, con una coloreación de sus aristas en dos colores, de manera tal que no presentan como subgrafos monocromáticos a ciertos tipos de grafos específicos. En ...
