Seminarios Alumnos 2015

2015-11-11:

Autor:  Eduardo Zuñiga, DIM, U Chile.

Dónde: Sala 33, DII

Cuándo: Miércoles 11 de Noviembre, 13:30

Título:  Estudio del mecanismo de asignación proporcional aplicado a redes de congestión
Abstract: En esta presentación estudiaremos el Mecanismo de Asignación Proporcional descrito por Kelly en 1997, pero aplicado a Redes de Congestión, donde lo que se busca repartir es la capacidad de los arcos entre jugadores estratégicos que cuentan con caminos en la Red, a través de los cuales pretenden enviar flujo. En primer lugar, se analiza el problema de unicidad del Equilibrio de Nash para el mecanismo, y se logra probar que el Equilibrio es único para el caso en que los jugadores tienen un sólo camino de interés en la Red (esto se denomina Fixed Routing). El análisis se hace por casos, primero se estudia una Red donde todas las capacidades de los arcos son iguales, y luego se generaliza al caso en que las capacidades son distintas. En segundo término, se define una versión secuencial del mecanismo, en que los jugadores no entregan sus valoraciones simultáneamente sino que van jugando en orden. Se prueba para el caso de dos jugadores, que el Equilibrio perfecto en Subjuegos es único, y que el Precio de la Anarquía asociado es 7/8, lo que mejora la eficiencia del mecanismo simultáneo.

2015-10-14:

Autor:  Jorge Mesías Moreno, Instituto Economía, PUC.

Dónde: Sala 33, DII

Cuándo: Miércoles 14 de Octubre, 13:30

Título:  Diseño de mecanismo eficiente con adquisición de información dinámica
Abstract: Este trabajo aborda un problema de asignación de bienes cuando los demandantes no conocen el bien en cuestión, lo que hace que no conozcan su verdadera valoración por el objeto. De esta situación, sumado a la restricción de una experimentación por periodo, surge el problema de adquisición de información dinámica. Tres principales resultados se entregan a lo largo del trabajo. Primero, es posible caracterizar un orden eficiente siempre cuando los individuos se diferencian en priors, lo que no ocurre cuando la diferenciación es en costos de adquirir información. Segundo, es posible caracterizar la adquisición de información de un proceso con un número finito de familias diferentes en priors, tal que en el tiempo se adquiere cada vez menos información y no todas las familias disponibles experimentan. Tercero, existe un mecanismoex-post eficiente, cuando las valoraciones de los agentes son interdependientes.

2015-09-09:

Autor:  Giorgiogiulio Parra De Blasi, DII, U. Chile.

Donde: Sala 33, DII

Título:  Generación de benchmark de fondos para el sistema de pensiones en Chile, un enfoque basado en optimización estocástica.
Abstract: En el presente trabajo se resuelve el problema de portafolios de pensiones en Chile, utilizando para este fin, una metodología basada en la minimización de diferentes medidas de riesgo, tales como: Valor esperado (Expected Value), Valor Condicional en riesgo (Conditional Value at Risk (CVaR)), una combinación convexa de los dos anteriores (ECVaR) y la Medida de Riesgo Entropica (Entropic Risk Measure). La última de estas medidas de riesgo, en si misma constituye una contribución metodológica, dado que nunca habia sido resuelta en un problema de optimización de este tipo. Se logra conjeturar que la Medida de Riesgo Entropica, puede actuar como cualquiera de las otras medidas, ajustando adecuadamente su nivel de adversión, en particular como ECVaR, que como benchmark logra a través de inversiones permitidas, obtener mejores desempeños que los obtenidos por el Fondo A, en la ventana de tiempo 2003 a 2013.

2015-08-12:

Autor:  Andrés Perlroth, DII, U. Chile.

Donde: Sala 33, DII.

Título:  En búsqueda de una relación entre la complejidad estructural de un juego y su Precio de la Estabilidad y de la Anarquía.
Abstract: Extendemos el clásico modelo de remate combinatorial con jugadores mono-interesados para el caso cuando el martillero enfrenta una restricción en la asignación. Vía el Precio de la Estabilidad y de la Anarquía, buscamos vincular la complejidad del juego con la dificultad computacional de encontrar una solución factible para la restricción del diseñador. Nuestros resultados obtenidos muestran que tal relación no existe.

Este trabajo es realizado en conjunto con Andreas Schulz.

2015-05-13:

Autor:  Renaud Chicoisne, DII, U. Chile.

Donde: Sala 33, DII, 13.30-14.30

Título:  Reformulations for hard network problems
Abstract:   Easy combinatorial problems as finding a shortest path or a minimum cut in a directed network can quickly lose their good properties when adding extra constraints or considering a nonlinear objective function. As these problems turn NP-hard in general, we present new formulations for difficult network problems that have fewer integer variables. These formulations help derive constraint branching schemes that take advantage of the special structure of the problems.
We show how to apply these formulations and associated branching schemes to the st-path and the Hamiltonian circuit sets in general networks as well as the st-path and st-cut sets in Directed Acyclic Graphs (DAGs). This preliminary work shows promising ideas for the development of practical resolution schemes for hard network problems.

2015-04-08:

Autor:  Javiel Rojas, DCC, U. Chile.

Donde: Sala 33, DII, 13.30-14.30

Título:  The Klee’s measure and adaptive analysis
Abstract:   The Klee’s Measure of $n$ axis-parallel boxes in $d$-dimensional space is the volume of their union. It can be computed in time within $O(n^{d/2})$ in the worst case, and faster for large families of instances.  We describe two techniques to quickly reduce an instance to a serie of smaller ones, and one technique to refine the analysis of the previous $O(n^{d/2})$-time solution.
The first one takes advantage of instances where the \textsc{Maxima} of the input is of small size $h$, and yields a solution running in time within $O(n\log^{2d-2}{h}+ h^{d/2})$.  The second technique takes advantage of instances where the \emph{intersection graph} of the input has a small number $e$ of edges or a small number $\rho$ of connected components of respective sizes $n_1,\ldots,n_\rho$, and yields a solution in time within $O(n \log ^{2d-3}{n} + e + \sum_{i=1}^{\rho}{n_i^{d/2}})$.  The third technique takes advantage of instances where no $d$-dimensional axis-aligned hyperplane intersects more than $k$ boxes, for some value of boxes, and yields a solution running in time within $O(n \log n + n\sqrt{k})$ when d=3.

2015-03-11:

Autor:  Carlos Ochoa, DCC, U. Chile.

Donde: Sala 33, DII, 13.30-14.30

Título:  Aprovechando el Orden de la Entrada para Calcular la Envoltura Convexa
Abstract:   El cálculo de la Envoltura Convexa es un problema central en Geometría Computacional. En 2009, Afshani, Barbay y Chan demostraron que una variante del conocido algoritmo de Kirkpatrick y Seidel aprovecha de forma óptima la posición en la que son dados los puntos para agilizar el cálculo de la Envoltura Convexa. En 2002, Levcopolous et al. describieron un algoritmo que aprovecha el orden en que son dados los puntos en la entrada para calcular la Envoltura Convexa. Este algoritmo interpreta los puntos como una cadena poligonal, donde cada pareja de puntos consecutivos de la entrada determina biunívocamente una arista de la cadena. El tiempo de ejecución es $O(n \log{\chi}$, donde $n$ es el total de puntos y $\chi$ es el número mínimo de cortes que hay que hacerle a la cadena para que cada subcadena resultante sea simple, es decir, no se interseque con ella misma.

En esta charla presentamos un refinamiento en el análisis de la complejidad del algoritmo de Levcopolous et al., agregando a la complejidad la anchura del árbol de derivación resultante de la ejecución del algoritmo. Como trabajo futuro, consideramos la idea de diseñar un algoritmo que aproveche tanto la posición de los puntos como el orden en que estos son dados para calcular la Envoltura Convexa (combinando ambos análisis) y la extensión de estas técnicas al cálculo de la Triangulación de Delaunay.

Student Seminars 2014

2014-11-12:

Autor:  Nicolás Sanhueza, DIM, U. Chile.

Donde: Sala 33, DII, 13.30-14.30

Título:  Estructura y números de Ramsey para ciclos y ruedas de tamaño impar.
Abstract:   Estudiamos la estructura de arista-coloreaciones azul-roja de grafos completos, con ciertos subgrafos prohibidos asociados a cada color. Concretamente, estudiamos el caso en que los grafos prohibidos son el n-ciclo en el color rojo, y la n-rueda en el color azul; donde n es un entero impar. Nuestro resultado principal es que en cualquier coloreación de este tipo, borrando a lo más dos vértices, se obtiene una partición de los vértices en tres conjuntos tales que las aristas con ambos extremos en el mismo elemento de la partición tienen el color rojo; y el resto azul. Como resultado secundario de nuestra demostración, obtenemos cotas superiores para los números de Ramsey del (2k+1)-ciclo versus la 2j-rueda para k<j enteros, que son asintóticamente (en k) cercanas a los valores conjeturados.

2014-10-08:

Autor:  Christian von Borries, DIM, U. Chile.

Donde: Sala 33, DII, 13.30-14.30

Título:   Emparejamientos on-line en grafos bipartitos
Abstract:   En esta charla estudiaremos el siguiente problema de optimización: Dado un grafo bipartito, cuyos vértices llegan on-line, queremos construir un emparejamiento grande, pero restringido a emparejar solamente vértices en el momento que llegan. Este problema ha sido estudiado en el caso que un lado está fijo, en cuyo caso existe un algoritmo que es una (1-1/e)-aproximación, lo que es óptimo. Analizaremos el caso en el que vértices de ambos lados del grafo pueden llegar on-line en distintos modelos:

- El modelo adversarial, en el que un adversario elige el grafo y el orden en el que los vértices llegan on-line.

- El modelo de orden aleatorio, en el que un adversario elige el grafo y los vértices llegan en el orden de una permutación elegida uniformemente al azar.

- El modelo off-line, en el que el algoritmo sabe de antemano el grafo y el orden, pero tiene que mantener la competitividad en la llegada de cada vértice.

2014-09-10:

Autor:  Waldo Gálvez, DIM, U. Chile

Donde: Sala 33, DII, 13.30-14.30

Título:   Programación online de trabajos en máquinas paralelas usando migración acotada
Abstract:  En esta charla trataremos el problema de programar de manera online trabajos en máquinas paralelas idénticas. En este contexto cada trabajo está caracterizado por un tiempo de proceso, y nuestro objetivo es asignar los trabajos a un conjunto de máquinas tal que el trabajo total de las máquinas esté bien distribuido. En un ambiente online los trabajos son desconocidos y llegan una a uno.  Cada vez que llega un trabajo nuevo los trabajos previos pueden reasignarse, bajo la condición que el tamaño total de trabajos no sea más que proporcional al tamaño del trabajo nuevo. La constante de proporcionalidad se llama constante de migración, y mide cuan robustas son las soluciones construidas. Se estudiará el problema de maximizar la carga mínima, para el cual existe un algoritmo 2-competitivo usando un factor de migración 1, y se sabe que no existe un algoritmo mejor que 20/19-competitivo con factor de migración constante. Basado en un algoritmo de tipo glotón para el problema offline (LPT), se diseña un algoritmo (1.5 + eps)-competitivo usando un factor de migración O(1/eps). Finalmente se discutirán algunas ideas para poder cerrar la brecha de competitividad alcanzable con migración constante.

2014-08-13:

Autor: Mario Bravo, ISCI & DII, U. chile.

Donde: Sala 33, DII, 13.30-14.30

Título:   Algoritmos de aprendizaje adaptativo en Teoría de Juegos
Abstract:  En esta charla daremos un panorama general de algunas dinámicas que emergen del estudio de interacciones estratégicas en un juego repetido en tiempo discreto. La idea es encontrar reglas de decisión para los jugadores que les permitan adaptarse y reaccionar de manera satisfactoria a las estrategias sus oponentes.

Distinguiremos dos tipos fundamentales de dinámicas: las unilaterales y las globales. En una dinámica de tipo unilateral se asume que el comportamiento de todos los agentes dado por una regla de decisión precisa. En una unilateral, hay un agente que enfrenta a la naturaleza que se puede comportar de una manera arbitraria. Discutiremos, en ambos casos, nociones apropiadas de optimalidad en términos asintóticos.

Para finalizar, haremos especial hincapié en las dinámicas de información minimal. En este caso, se asume que los jugadores no conocen el juego y ni siquiera pueden observar las estrategias de sus oponentes. La única información que reciben es su propio pago en cada etapa.

2014-07-09 (seminario doble):

Autor: Carlos Ochoa, DCC, U. chile.

Donde: Sala 33, DII, 13.00-13.30

Título:  Algoritmos adaptativos para Covertura Convexa, Diagrama de Voronoi y Triangulación de Delaunay.
Abstract:  El diagrama de Voronoi y la triangulación de Delaunay son estructuras importantes que encuentran aplicaciones en geografía, física, astronomía, robótica, entre otros muchos campos. Ambas estructuras están estrechamente relacionadas. A sus propiedades y construcción se han dedicado un gran número de trabajos desde el siglo XVII, siendo aún un importante tema de investigación en Geometría Computacional. En esta charla presentaremos un algoritmo adaptativo para la construcción de la triangulación de Delaunay de un conjunto de puntos en el plano que se aprovecha del orden de los puntos en la entrada. Estos resultados extienden trabajos previos en compresión de permutaciones y mezcla de diagramas de Voronoi.

Autor: Javiel Rojas, DCC, U. chile.

Donde: Sala 33, DII, 13:30-14.00

Título:  El problema de la medida de Klee desde la perspectiva de la adaptabilidad.

Abstract: La medida de Klee de un conjunto de cajas d-dimensionales se define como el volumen de la unión de las cajas en el conjunto. Desde que se planteó en 1977 hasta la actualidad se han propuesto varios algoritmos, el más eficiente de todos dado a conocer hace apenas un año. Aunque el problema ha sido analizado en varios modelos de computación y se han estudiado casos especiales del mismo no se ha encontrado ningún algoritmo adaptativo que resuelva el problema (y los algoritmos existentes nunca han sido analizados desde el punto de vista de la adaptabilidad).

Proponemos un algoritmo adaptativo para este problema que se beneficia de la degeneración por dominación de una entrada.  Aunque bastante simple, este algoritmo permite ilustrar que se puede ser más fino en el análisis de este problema. Discutimos además potenciales medidas de dificultad para una instancia de entrada que pudieran ser utilizadas en un futuro algoritmo adaptativo para resolver el problema.

 

2014-06-11:

Autor: Andrés Perlroth, DII, U. chile.

Donde: Sala 33, DII, 13.30-14.30

Título:   Política óptima de precios frente a consumidores estratégicos
Abstract:  Estudiamos un modelo de revenue management donde un vendedor elige una política de precio en el tiempo para vender un único ítem. Dada dicha política, compradores estratégicos llegan estocásticamente en el tiempo y deben decidir cuando comprar el producto considerando el riesgo de no obtenerlo. Suponiendo dos tipos de compradores, unos de alta y otros de baja valoración, probamos existencia de equilibrio en el problema de decisión de compra cuando la política de precio es continua. Además caracterizamos la política de precio que maximiza las ganancias del vendedor sobre un basto conjunto de posibles funciones de precio. Este trabajo fue realizado en conjunto con Luis Briceño y José Correa.

 

2014-05-14:

Autor:  Roberto Konow, DCC, U. chile.

Donde: Sala 33, DII, 13.30-14.30

Título:   Treaps Invertidos: Intersecciones y uniones rápidas sobre conjuntos
Abstract: Presentaremos una nueva estructura de datos que realiza intersecciones y uniones más rápidas utilizando menos espacio. Esta representación esta basada en la estructura de datos Treap, que permite intersectar/unir los elementos. Para reducir el espacio que esta estructura utiliza, representamos la topología del árbol usando estructuras de datos compactas. Además, las propiedades del treap permiten codificar de forma diferencial los valores del conjunto. Resultados empíricos muestran que el uso de espacio es menor al 10% del espacio utilizado por los datos originales y que la estructura es capaz de realizar consultas hasta dos veces mas rápidas que otras representaciones que requieren más espacio.

 

2014-04-09:

Autor:  Alberto Vera, DII, U. chile.

Donde: Sala 33, DII, 13.00-14.00

Título:   Rumor spreading en redes sociales
Abstract: Estudiamos el problema de rumor spreading en redes sociales, donde los agentes se comunican y propagan un rumor de forma aleatoria. Buscamos contagiar a toda la red en tiempo finito a mínimo costo. Proponemos un algoritmo adaptativo, que monitorea continuamente el estado de la red y decide en cada momento si intervenir o no. Damos una descripción del algoritmo óptimo y mostramos que requiere mirar la red sólo un número finito de veces. Formulamos además el caso cuando el número de agentes tiende a infinito como un problema de control, y mostramos que la estrategia óptima es no intervenir.

 

2014-03-12:

Autor: Mauro Escobar, DIM, U. chile.

Donde: Sala 33, DII, 13.00-14.00

Título:  Análisis de Algoritmos de Codificación
Abstract: En esta charla se tratará un problema de transmisión de datos bajo el contexto de network coding. Específicamente, se considera un sistema con un transmisor y dos receptores. Se considera, también, que el tiempo transcurre de manera discreta. La información que se desea enviar está dividida en paquetes (los cuales se modelan como vectores en un espacio vectorial) y llega al transmisor mediante un proceso de Bernoulli de tasa $\lambda$. El transmisor puede enviar, en cada período, una combinación lineal de paquetes por igual a cada uno de los receptores. Las transmisiones pueden fallar en cada período con probabilidad $1-\mu$ de manera independiente entre cada receptor. Los receptores deben ser capaces de recuperar cada paquete de información original. En este contexto, se desea estudiar el tiempo que tarda un paquete entre que llega al transmisor y es decodificado por los receptores, bajo un algoritmo de codificación de paquetes que realiza el transmisor al enviar la información. Se realiza un análisis asintótico cuando $\mu$ tiende a $\lambda$.

 

2014-01-15:

Autor: Víctor Verdugo, DII, U. chile.

Donde: Sala 33, DII, 13.00-14.00

Título: Programación de trabajos divisibles en máquinas paralelas
Abstract: En esta charla se tratará el problema de programar trabajos en un ambiente de máquinas paralelas idénticas. En este contexto los trabajos pueden ser divididos en distintas partes, cada una de las cuales puede ser procesada de manera independiente. Antes de procesar cualquier parte de un trabajo, la máquina debe prepararse y requiere un tiempo de instalación. Primero se estudia el problema de minimizar la suma ponderada de tiempos de completación, para el cual se obtiene una $(2+\epsilon)$-aproximación cuando los tiempos de instalación son todos iguales. Este resultado corresponde al primer algoritmo de aproximación de factor constante para esta función objetivo. Usando técnicas similares se diseña una 2-aproximación para el caso de una ponderación uniforme de los trabajos, que en particular mejora el factor 2.781 obtenido por Schalekamp et al. el 2012. Finalmente, con un algoritmo de programación en lista se obtiene una 4-aproximación para el problema de minimizar la suma ponderada de los tiempos de completación y con tiempos de instalación dependientes del trabajo.

 

Eduardo Zuñiga