Ingeniero Civil Matemático / El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.

Ingeniero Civil Matemático / El propósito de esta memoria es estudiar un modelo de aprendizaje en juegos repetidos. A diferencia de otros esquemas estudiados en la literatura, en este caso se estudia una situación en que los jugadores disponen de muy poca información, pudiendo observar solamente el pago recibido en cada etapa pero sin observar las estrategias usadas por los demá́s jugadores ni sus correspondientes pagos. En base a la información individual recolectada a medida que se desarrolla el juego, cada jugador genera una percepción del pago esperado de las distintas estrategias puras, y en base a estas percepciones adapta su comportamiento para las siguientes etapas del juego. En el capítulo 1 se presentan los modelos de las principales referencias bibliográficas, junto a los resultados mas relevantes que allí se obtienen. Se definen además las instancias y variantes a los modelos anteriores con las que se trabajará a lo largo de esta memoria. El capítulo 2 contiene todas las herramientas técnicas y conocimientos previos que fueron necesarias para desarrollar los resultados obtenidos. Se comienza con una sección de introducción a la topología diferencial, cuya principal referencia es el texto Topology from the differentiable viewpoint de Milnor, donde el resultado de mayor interés es el conocido Teorema de Poincaré-Hopf. En la siguiente sección se describen resultados referentes a martingalas, diferencias de martingalas y algunos teoremas de convergencia. La última sección está dedicada a estudiar los algoritmos de aproximación estocástica, basado en trabajos de las principales referencias en el tema, como Benaïm, Chen y Kushner. El capítulo 3 está dedicado a estudiar el proceso de aprendizaje propuesto, que consiste en una regla de actualización de las percepciones de los jugadores sobre su espacio de estrategias puras al enfrentarse a un juego repetido, los resultados asintóticos (cuando la iteración n tiende a ∞) guarda estrecha relación con una dinámica continua asociada, cuyos puntos estacionarios corresponden a los equilibrios de Nash de un juego potencial subyacente. Bajo la regla de decisión Logit y algunas condiciones sobre los parámetros del modelo, se obtienen interesantes resultados de convergencia casi segura y con probabilidad positiva a atractores de la dinámica continua. Finalmente en el capítulo 4 se estudia el modelo de Cominetti et al. [7], para unas instancias específicas (caso de 2 y 3 jugadores con 2 rutas) con el objetivo de contar a cantidad de equilibrios del sistema.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Cada semi-grupo tiene asociado un generador infinitesimal. Hille y Yosida descubrieron de manera independiente, alrededor de 1948, una condición necesaria y suficiente para saber cuándo un operador es el generador infinitesimal de un semi-grupo (de clase C0). Por otro lado, cada semi-grupo tiene asociado un potencial, concepto dual al de generador infinitesimal. Hunt, Meyer y Lion, entre otros, encontraron condiciones para saber cuándo un operador es el potencial de un semi-grupo. El problema propuesto para esta tesis es el siguiente : dado el núcleo de Green del movimiento browniano en un dominio, ¿ qué potencias de este núcleo y sobre qué clase de dominios generan un potencial de semi-grupo ? La idea central para resolver este problema es la aproximación del núcleo por procesos discretos, usar resultados conocidos para matrices y extender estos resultados al caso continuo. Para que funcione la aproximación, es necesario restringir la clase de conjuntos considerados, tratando de quedar lo más general posible. En esta tesis damos respuesta para el caso de los abiertos acotados regulares. Los conjuntos regulares son, simplificando, los conjuntos adecuados de la teoría del potencial. Si se debe resumir la memoria en una palabra seria «aproximación», se trata de reducir el problema a un caso conocido y se busca como extenderlo. / Este trabajo ha sido parcialmente financiado por el CMM Center for Mathematical Modeling

El principal objetivo de estudio de esta tesis son los mecanismos eficaces y eficientes para computar respuestas en formalismos de argumentación estructurada probabilística, en particular, en el modelo DeLP3E. Dicho formalismo nos permite modelar y razonar sobre información inconsistente, incompleta, y asociada a eventos probabilísticos. En particular, el objetivo es estudiar y proponer mecanismos que nos permitan aproximar las respuestas por medio de algoritmos que se basen en toda la información disponible de cada componente del modelo. Nos enfocamos en investigar este aspecto dado que, dar una respuesta exacta a una consulta en DeLP3E no es aplicable en un tiempo razonable para instancias grandes. La principal contribución de esta tesis es la definición y estudio de algoritmos, junto con una guía para seleccionar cuál de ellos aplicar, que nos permitan aproximar el valor de una respuesta en base a toda la información disponible en el modelo DeLP3E. A su vez, y con la finalidad de poder evaluar el desempeño no de los algoritmos propuestos, otra importante contribución de esta tesis son tres generadores para crear modelos DeLP3E. Cada uno de estos generadores nos permite crear diferentes escenarios de complejidad de manera automática, y teniendo como principal característica que los valores de sus métricas son ajustables en base al valor de los parámetros de entrada que guían el proceso de generación. A su vez, y para mostrar un caso de uso de lo desarrollado en esta tesis, se presenta P-DAQAP, una plataforma web que facilita el análisis de los proceso llevados a cabo en el modelo DeLP3E y en la Programación Lógica Rebatible (DeLP, en inglés). Se mostró, a través de casos de uso y ejemplos prácticos, que una herramienta de este tipo puede ser de gran utilidad para usuarios que requieran analizar dominios complejos y que tengan eventos probabilísticos asociados. Además de esa utilidad en entornos reales, también puede ser usada con fines educativos, ya que ofrece un conjunto de herramientas gráficas para facilitar la lectura y entendimiento de los procesos argumentales llevados a cabo en el formalismo DeLP. P-DAQAP es una herramienta pública que consideramos de gran utilidad para la comunidad de argumentación estructurada. / The main objective of this thesis is the study of the effective and efficient mechanisms to compute answers in formalisms of probabilistic structured argumentation, in particular, in the DeLP3E model. This formalism allows us to model and reason on inconsistent and incomplete information, as well information associated with probabilistic events. In particular, the objective is to study and propose mechanisms that allow us to approximate the answers by algorithms that are based on all the available information of each component of the model. We focused on investigating this aspect since giving an exact answer to a query in DeLP3E is not applicable in a reasonable time for large instances. The main contribution of this thesis is the definition and study of algorithms, and a guide to select which of them to apply, which allow us to approximate the value of a response based on all the information available in the model DeLP3E. Also, and in order to be able to evaluate the performance of the proposed algorithms, another important contribution of this thesis is three generators to create DeLP3E models. Each of these generators allows us to create different complexity scenarios automatically, and having as main characteristic that the values of their metrics are adjustable based on the value ofthe input parameters that guide the generation process. Also, and to show a use case of what has been developed in this thesis, P-DAQAP is presented, a web platform that facilitates the analysis of the processes carried out in the DeLP3E model and in Defeasible Logic Programming (DeLP). It was shown, through use cases and practical examples, that a tool of this type can be very useful for users who need to analyze complex domains and have associated probabilistic events. In addition to this utility in real environments, it can also be used for educational purposes, since it offers a set of graphic tools to facilitate the reading and understanding of the argumentative processes carried out in the DeLP formalism. P-DAQAP is a public tool that we consider very useful for the structured argumentation community.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Hace algunas décadas ha nacido dentro de la investigación de operaciones la subdisciplina denominada sports scheduling, la cual se propone abordar los problemas y desafíos que se presentan en el diseño de torneos deportivos. Esta tesis pretende ser una contribución al área de sports scheduling dentro del contexto del fútbol profesional chileno. Su objetivo es modelar de modo conjunto los dos principales torneos del fútbol profesional chileno, la Primera A y la Primera B, utilizando instancias basadas en la temporada 2015-2016. Debido a la complejidad del modelo, que es consecuencia de la enorme cantidad de restricciones y de variables que contiene, una resolución directa por medio de un solver estándar actual no entrega resultados en tiempos razonables. Por ello, es necesario desarrollar una estrategia que permita disminuir los tiempos de resolución. Esta estrategia está basada en el empleo de patrones asociados a equipos, los cuales establecen sus secuencias de localías y visitas. La estrategia desarrollada consiste en una metodología secuencial que comienza con la obtención de patrones por medio de un modelo generador que considera las restricciones básicas del problema, entre las cuales se encuentran aquellas que fijan localías y visitas de antemano. Posteriormente, los patrones obtenidos son asociados a los equipos en el modelo principal, con lo cual se asegura que al comienzo de su resolución las restricciones básicas estén satisfechas. Luego, se intenta incluir la mayor cantidad de las restricciones faltantes dejando fijos todos los patrones. Para aquellas restricciones que no se haya podido incluir, se puede relajar de 2 a 4 patrones hasta que se encuentre un nuevo conjunto de patrones factibles. Los resultados obtenidos al aplicar la estrategia descrita son satisfactorios. La mayor parte de las restricciones se incluye fijando los patrones obtenidos por el modelo generador de patrones, mientras que la relajación de algunos de ellos permite agregar las restantes. Los tiempos de resolución son razonables, pues el mayor de ellos, correspondiente al del modelo que considera todas las condiciones impuestas sobre la temporada 2015-2016, es menor a media hora.

No description available.

En este trabajo se analizó la factibilidad de alcanzar los límites de descarga de efluentes impuestos por el DSN°90/200, a través, de la evaluación de alternativas de remoción biológica de nutrientes que permitan cumplir con los requerimientos de calidad y/o conlleven optimizar el funcionamiento de los sistemas de tratamiento de aguas servidas.

Doctor en Sistemas de Ingeniería / En este trabajo se estudia la calidad que ofrecen las soluciones óptimas locales para problemas de programación de tareas en máquinas en paralelo. Los ambientes considerados son máquinas idénticas, idénticas restringidas, uniformes restringidas y no-relacionadas. El objetivo considerado es la minimización del tiempo ponderado de completación. Para estudiar la calidad de los óptimos locales se determinan los factores de aproximación para las soluciones localmente óptimas de los vecindarios de inserción (jump) e intercambio (swap). Los resultados indican que para los ambientes de máquinas paralelas uniformes y no-relacionadas, el costo de cualquier óptimo local se encuentra alejado a lo más en un factor 2,618 con respecto al costo del óptimo. Si solo se considera la minimización del tiempo de completación, se tiene que el factor es 2. El mismo resultado se obtuvo para el ambiente de máquinas uniformes con tareas unitarias, para los casos ponderado y no ponderado. Por otra parte, para el problema de máquinas paralelas idénticas restringidas, se determinó que el factor de aproximación se encuentra entre 1,75 y 1,809. Para el caso no ponderado este factor se encuentra entre 1,5333 y 1,618. Para el caso de tareas unitarias, donde el objetivo es la minimización del tiempo ponderado de completación, se determinó que el factor de aproximación se encuentra entre 1,5333 y 1,618. Mientras que para el caso no ponderado se tienen evidencias que indican que el factor de aproximación es 1,5333. / Este trabajo ha sido parcialmente financiado por Universidad del Bío-Bío; Conicyt, Programa de Formación de Capital Humano Avanzado; Núcleo Milenio Información y Coordinación en Redes

No description available.

This doctoral thesis is devoted to the analysis of orthogonal sequences in subspaces of spaces L2(m) of square integrable functions with respect to a Banach space valued countably additive measure m. The motivation of our work is to generalize the geometric arguments that provide the classical approximation procedures in Hilbert spaces. The notion of orthogonality lies in the center of the Hilbert space theory, and it allows to develop the theory of convergence of sequences in these spaces. Almost everywhere convergence, norm convergence and weak convergence are nowadays well known topics in the Hilbert space function theory. The Banach function spaces L2(m) of a vector measure m represent a broad class of Banach lattices: each 2-convex order continuous Banach lattice with a weak unit can be represented (by means of an order isomorphism) as a space L2(m) for an adequate vector measure m. The integral structure that the vector measure integration provides in these spaces allows to generalize the orthogonality arguments of the Hilbert space theory, although the spaces L2(m) are far from being Hilbert spaces. The first chapter of this memoir is devoted to introduce some fundamental concepts on Banach function spaces, vector measure integration and other topics that will be necessary in the rest of the work. Some results on convergence of sequences in Banach function spaces and Banach spaces are explained, and the general framework is established. Some orthogonality arguments are already introduced, both for sequences in L2(m) and for the integrals of these sequences when the vector measure m is Hilbert space valued. Unconditional convergence for sequences from the abstract point of view of the function spaces of integrable functions is analyzed, and a version of the Kadec and Pelczynsky method for finding disjoint sequences for the vector measure setting is given. In the second chapter three notions of orthogonality of a sequence with respect to a vector measure are formally introduced, and the main characterizations of these sequences are given. Weak m-orthogonal sequences, (natural) m-orthogonal sequences and strongly m-orthogonal sequences are de ned and studied, providing also examples that show the relation with some classical problems in analysis. The geometry of these sets of sequences are also studied. In Chapter 3 we analyze almost everywhere convergence of weakm-orthogonal sequences. Our main result is a general vector measure version of the Mencho - Rademacher Theorem. A particular case involving c0-sums of Hilbert spaces is also intensively studied in order to show the properties of the convergence. Finally, Chapter 4 is devoted to show a concrete application. We develop an approximation method with respect to a parametric measure based on our ideas. A Bochner integrable function and an weak m-orthonormal sequence are the main elements of our procedure, that allows to nd the Fourier coefficients -that are in this case measurable functions- for a given function in the space L2(m). Some applications for signal approximation for data coming from experimental acoustics are also shown. / Jiménez Fernández, E. (2011). Vector measure orthogonal sequences in spaces of square integrable functions [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/13832 / Palancia