Seminario Alumnos 2016

2016-11-09:

Autor:  Sebastian Perez, DIM, U Chile.

Dónde: Sala 33, DII.

Cuándo: Miércoles 07 de Diciembre, 13:30.

Título:  El problema de la degenerancia en el Congested Clique

Abstract:  La degenerancia de un grafo G, d(G), se define como el mínimo entero k tal que todo subgrafo de G tiene un vértice de grado a lo más k. La degenerancia se utiliza como una medida de esparcidad del grafo, por ejemplo, los bosques tienen degenerancia a lo más 1 y los grafos planares tienen degenerancia a lo más 5. La degenerancia es esencialmente un parámetro “secuencial” que en computación centralizada, puede ser calculada removiendo iterativamente el vértice de grado mínimo. Sin embargo, resultados recientes, muestran que si queremos resolver algunos problemas que surgen de manera natural en sistemas distribuidos, donde G en vez de ser un grafo abstracto es una red de procesadores, entonces los procesadores necesitan calcular la degenerancia de la red. En otras palabras, calcular la degenerancia parece ser un paso crítico si deseamos resolver problemas relevantes en sistemas distribuidos.

En esta presentación se considerará el modelo de computación distribuida Congested Clique. Se presentará como aproximar la degenerancia cuando los procesadores se comunican por comunicación de tipo Unicast y por comunicación de tipo Broadcast.

En Unicast se diseña un protocolo aleatorizado de O(log n) rondas, usando mensajes de largo O(log n) para calcular una (1+ε)-aproximación de la degenerancia. Esencialmente, el protocolo toma una “buena muestra” del grafo de entrada que cumple dos importantes propiedades. Primero, la muestra aproxima bien el ordenamiento degenerado del grafo original. Segundo, la muestra es pequeña lo cual asegura que puede ser distribuida eficientemente.

En Broadcast se diseña un protocolo determinista de O(log n) rondas, usando mensajes de largo O(log n) para calcular una (2+ε)-aproximación de la degenerancia. En este caso, se intenta simular la secuencia ordenada utilizada por el algoritmo centralizado.

2016-11-09:

Autor:  Simon Piga, DIM, U Chile.

Dónde: Sala 33, DII.

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

Título:  Números de Ramsey y Turán para Coloreos Promedio en Grafos Completos

Abstract:  El número de Ramsey de k colores para un grafo G corresponde al mínimo n tal que cualquier coloreo de las aristas de K_n con k colores distintos, contiene una copia monocromática de G. Por otro lado, el número de Turán k-coloreado de G para n vertices, corresponde al maximo número de aristas que puede tener un grafo de n vértices, de manera que no contenga una copia una copia monocromática de G para algún coloreo de k colores.
Es posible plantear los problemas anteriores utilizando versiones más generales de coloreos, en que la cantidad total de colores no es fija. En particular en coloreos locales y promedio. En un k-coloreo local, cada vértice es incidente a aristas de a los más k colores diferentes, en cambio en un k-coloreo promedio, el número promedio de colores incidente a cada vértice es a lo más k.
Si bien los coloreos promedios son más generales que los locales, la pregunta de si los números de Ramsey (o Turán) locales y promedio son iguales aun sigue abierta, y se ha respondido afirmativamente para importantes familias de grafos. En esta presentación en particular observaremos el caso de grafos completos.

2016-10-18:

Autor:  Andrés Cristi, U Chile.

Dónde: Sala 33, DII.

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

Título:  Estabilidad de asignación de estudiantes a colegios con privilegio de que hermanos estén juntos.

Abstract:  En un mercado de asignación entre dos conjuntos disjuntos W y M, una asignación estable es una asignación tal que no existe un par w en W, m en M que se prefieren mutuamente por sobre sus asignaciones correspondientes. Se puede probar que bajo supuestos razonables siempre existe una asignación estable y hay un algoritmo relativamente simple que la encuentra. Se sabe además que hay una manera centralizada de escoger la asignación de manera que para uno de los lados la estrategia óptima sea revelar sus verdaderas preferencias.
Por tan deseables propiedades, este esquema es usado en distintas ciudades del mundo para asignar estudiantes a cupos en colegios. Estudiaremos una extensión de la noción de estabilidad al caso en que hay familias que tienen como prioridad que sus hijos queden en el mismo colegio y mostraremos que en este contexto no se puede garantizar la existencia de una asignación estable.

2016-08-10:

Autor:  Patricio Foncea, DII, U Chile.

Dónde: Sala 33, DII.

Cuándo: Miércoles 10 de Agosto, 13:30.

Título:  Remate Posted-Price con Orden Aleatorio

Abstract:  Consideramos el problema que enfrenta un agente que desea vender un bien a uno de varios potenciales compradores. En 1981 Myerson caracterizó la regla de asignación y los precios que deben ser cobrados para obtener un remate óptimo que maximice la utilidad del vendedor. En este caso, estudiamos una restricción del problema donde los clientes llegan en orden aleatorio a demandar el ítem: por orden de llegada se le ofrece a cada comprador un único precio, quien debe decidir si lo rechaza — perdiendo la posibilidad de volver a participar — o lo acepta, quedándose con el ítem y terminando el remate.

Presentaremos un algoritmo en base a una relajación lineal del problema que alcanza una (1-1/e)-aproximación del remate óptimo. Veremos además que este factor es ajustado.

2016-06-29:

Autor:  Felipe Contreras, DIM, U Chile.

Dónde: Sala 21, DII.

Cuándo: Miércoles 29 de Junio, 13:30.

Título: Particiones convexas en productos cartesianos de grafos.

Abstract:  Un conjunto de vértices de un grafo se dice convexo si ningún camino mínimo entre vértices del conjunto se sale de éste. En general, el problema de determinar si un grafo tiene un partición en convexos de tamaño p es NP-completo. Sin embargo, hay familias importantes de grafos en las que se puede determinar en tiempo polinomial, como los grafos cordados, los cografos o los grafos bipartitos.

En esta presentación, revisaremos el problema en productos cartesianos de grafos, en donde ciertas familias de grafos nos permiten reducir el problema a encontrar particiones solo en una coordenada.

2016-05-11:

Autor:  Javiel Rojas, DCC, U Chile.

Dónde: Sala 21, DII

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

Título: Adaptive analysis of algorithms in high dimensions.

Abstract:  An algorithm is said to be adaptive if “easy” instances are solved faster than the “hard” ones. We describe adaptive algorithms for three problems: the computation of the KLEE’S MEASURE, the MAXIMUM DEPTH, and the DEPTH DISTRIBUTION, respectively, of a set $B$ of $n$ axis-aligned boxes in a $d$-dimensional space. The KLEE’S MEASURE of $B$ is defined as the volume of the union of its boxes; and the MAXIMUM DEPTH as the maximum number of elements in $B$ containing any common point. The DEPTH DISTRIBUTION of $B$ is the vector $[V_1, V_2,..., V_n]$ with the volumes $V_i$ of the regions covered by exactly $i$ boxes from $B$. There are algorithms computing the KLEE’S MEASURE and the MAXIMUM DEPTH of $B$, respectively, in time within $O(n^{d/2})$. We explore the relation between the three problems; show that the DEPTH DISTRIBUTION of $B$ can be computed in time within $O(n^{(d+1)/2}\log n)$ in the worst case; and describe different measures of difficulty for the three problems, providing algorithms adaptive to these measures.

2016-04-13:

Autor:  Matias Pavez, DIM, U Chile.

Dónde: Sala 33, DII

Cuándo: Miércoles 13 de Abril, 13:30

Título:  Iteración de Krasnoselskii-Mann y Puntos Fijos

Abstract:  Uno de los métodos más comunes para encontrar puntos fijos de un operador no expansivo T:C\to C es la iteración de Krasnoselskii-Mann definida por

x_{n+1} = (1-\alpha_{n+1})x_n + \alpha_{n+1}Tx_n

Resulta que las cantidades |x_n-x_m| tienen relación con cierto proceso aleatorio sobre los enteros, del cual es posible deducir una cota para la regularidad asintótica |x_n-Tx_n| que sólo depende de la sucesión \{\alpha_k\}.

En esta presentación estudiaremos una variante de la iteración de Krasnoselskii-Mann al introducir un término de error en el cálculo del punto Tx_n. Esta iteración también tendrá relación con un proceso aleatorio similar al de la iteración original. Mediante esta interpretación es posible dar una cota para la cantidad |x_n-Tx_n| que sólo depende los valores de \{\alpha_k\} y los errores.

2016-03-16:

Autor:  Carlos Ochoa, DCC, U Chile.

Dónde: Sala 33, DII

Cuándo: Miércoles 16 de Marzo, 13:30

Título:  Synergetic sorting

Abstract:  Munro and Spira (1976) described several sorting algorithms that take advantage of the structure of the instance (i.e., the multiplicities of the distinct elements) in order to sort a Multiset. Knuth (1973) considered sequences formed by runs (i.e., contiguous increasing subsequences) and described a sorting algorithm that takes advantage of the order in the input (i.e., the number and sizes of runs). We describe two new synergetic sorting algorithms, which take advantage of both the structure and the order of the input. These algorithms are not only always asymptotically as good as previous solutions taking advantage of any of the features previously mentioned, but which are much better on some instances where they can take advantage of both features at the same time. As an interesting side result, we described a compress data structure that supports rank and select queries based on the certificate that build these algorithms.

2016-01-21:

Autor:  Emilien Garcia, DIM, U Chile.

Dónde: Sala 33, DII

Cuándo: Jueves 21 de Enero, 13:30

Título:  Estudio de Variantes del Problema de la Secretaria

Abstract: El Problema de la Secretaria (SP) y sus variantes tienen mucho interés desde los años 50. Estudiamos la variante llamada Problema de la Secretaria con Restricciones de Tiempo (TCSP). Se define a través de una formulación discreta con N candidatos, y una formulación contínua con una infinidad de candidatos. En ambos casos se define un sampleo inicial en el cual se deben rechazar todos los candidatos entrevistados, y luego se quiere contratar al mejor de los candidatos que quedan.

Probamos propiedades que cumple la regla óptima que resuelve el (TCSP) discreto. Para encontrar sus propiedades cuando N tiende a infinito, extendemos esta regla a la versión contínua del (TCSP). Finalmente presentamos una extensión del (TCSP) a una versión donde el empleador tiene memoria eficiente sólo para recordar un único candidato del sampleo, y se encuentra la regla óptima de selección asociada.