Seminarios 2010


Author: Tomás González

Title: Complejidad Suavizada del Algoritmo Boyer-Moore-Horspool



Author: Pablo Moisset de Espanes

Title: Influencia del paralelismo en la dinámica de redes booleanas aleatorias



Author: Jose Verschae (joint work with M. Skutella and A. Wiese)

Title: Online robust minimum spanning trees

Abstract: Combinatorial optimization problems are usually unstable: slight changes on the instance of a problem can render huge changes in the optimal solution.

Thus, a natural question arises: Can we achieve stability if we only maintain approximate solutions? We study the classic minimum spanning tree problem in this setting.

More precisely, given a metric graph we want to construct a spanning tree that has a constant factor performance guarantee and is robust.

That is, if a new node is added to the graph we want to maintain the performance guarantee by only changing a constant number of edges in our tree.
In this talk I give some ideas of how to analyze a simple greedy algorithm for this problem



Author: Sebastian Marban

Title: The performance of SEPT in Bayesian Scheduling

Abstract: We consider the following scheduling problem: two classes of independent jobs have to be processed by a single machine so as to minimize the sum of expected completion times.

The processing times are assumed to be exponentially distributed with parameters A and B, depending on the class of the job.
We adopt a Bayesian framework in which A is assumed to be known, whereas the true value of B is unknown and is given the gamma prior distribution.

In this seminar, we show that in the Bayesian framework the performance of a policy that always processes a job with shortest expected processing time (SEPT) is at most a factor 2 away from the performance of an optimal policy.

Furthermore, we construct instances for which this bound is tight.

Finally, we discuss the possibility of extending the model to multiple job classes



Author: Alexandre Freire

Title: A branch-and-price scheme for the maximum edge biclique packing problem

Abstract: A biclique is a complete bipartite graph.

Given a (L,R)-bipartite graph G = (V,E) and a positive integer k, the maximum edge biclique packing (MEBP) problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset S of V and the number of edges inside the bicliques is maximized.

The maximum edge biclique (MEB) problem is a special case of the MEBP problem in which k is fixed as 1.
In this seminar, we introduce a new formulation for the MEB problem and a branch-and-price scheme for the MEBP problem



Author: Jeremy Barbay

Title: LRM Trees: Compressed RMQ Index, Adaptive Sorting, Compressed Permutations

Abstract: LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks, and to express the relative position of the first element of each block within a previous block.

They were used to encode ordinal trees and to index integer arrays in order to support range minimum queries on them.
We describe how they yield many other convenient results in a variety of areas, from data structures to algorithms: some compressed succinct indices for range minimum queries; a new adaptive sorting algorithm; and a compressed succinct data structure for permutations supporting direct and indirect application in time all the shortest as the permutation is compressible.
This is a joint work with Johannes Fischer



Author: Marcos Goycoolea

Title: Proximal cutting planes



Author: Terence Bayen

Title: Semidefinite programming for optimizing convex bodies under width constraints

Abstract: We consider the problem of minimizing a functional (like the area, perimeter, surface) within the class of convex bodies whose support functions are trigonometric polynomials.

The convexity constraint is transformed via the Fejér-Riesz theorem on positive trigonometric polynomials into a semidefinite programming problem.

Several problems such as the minimization of the area in the class of constant width planar bodies, rotors and space bodies of revolution are revisited.

The approach seems promising to investigate more difficult optimization problems in the class of three-dimensional convex bodies



Author: Tomas Veloz

Title: Quimica Algebraica, Problemas, Definiciones y Algoritmos

Abstract: Las Químicas Algebraicas son una modelo abstracto para la bioquímica.

Una Química Algebráica se compone de una red de reacciones moleculares, prescindiendo de una dinámica que permita estudiar su evolucion, pues el modelo se enfoca en como las moleculas pueden ser producidas o consumidas por las reacciones.

Se ha probado que un tipo especial de subredes, llamadas organisaciones, son las unicas subredes que pueden tener estabilidad dinamica, una vez que es incorporada una dinamica en el modelo.

Este hecho permite simplicar la comprension de la dinamica de los sistemas bioquímicos, dado que permite explicar la dinamica del sistema como movimientos entre organisaciones en el espacio de fase.

De aquí que el computo del conjunto de organizaciones de una Química Algebráica es una tarea central en la teoría. Al momento no han hay sucientemente buenos algoritmos para computar organisaciones, ni hay una comprensión de la estructura que subyace en la denición de organizacion (tal vez es esto es la razon de lo anterior). Esta tesis es un intento por formalizar el trabajo algorítmico en Químicas Algebráicas.

Dicha formalizacion busca una fertilizacion cruzada entre modelos de Ciencias de la computación y Químicas Alegebráicas.
Es posible enmarcar las Químicas Algebráicas en algunos conocidos formalismos de la Ciencia de la computacin como Sistema de Adicin de Vectores y Redes de Petri.

Se investiga la equivalencia entre los formalismos mencionados y las Químicas Algebráicas.
Luego algunos conocidos problemas de los Sistemas de Adicion de Vectores y Redes de Petri tales como reachability, liveness, etc., son estudiados desde la perspectiva de las Químicas Algebraicas, enfocando el analisis a la relacion de dichos problemas con el problema de computar organizaciones.

Las ideas que surgen del anterior analisis, se presentan varios resultados sobre el computo de organizaciones, asi como sobre la estructura del conjunto total de organizaciones de una Química Algebráica.
Los resultados de este trabajo hacen posible el desarrollo de nuevos y mas ecientes algoritmos para el computo de organizaciones y permite separar diferentes clases de Químicas Algebraicas en terminos de la dicultad de computar su conjunto de organizaciones



Author: Guillaume Theyssier, CNRS-Université de Savoie

Title: Directionnal dynamics in cellular automata

Abstract: When modeling natural phenomena by cellular automata, the following question arises naturally: is it possible to make long term predictions with only partial knowledge of initial conditions? This question has been extensively studied in the literature using tools from topological dynamics (e.g., in the work of P. Kurka). In this talk, following the framework of directional dynamics introduced recently by M. Sablik, we will tackle the question with a more discrete point of view: knowing only that some finite word u occurs somewhere in the initial configuration, what can be said with certainty about the future steps? what is the shape of theconsequences of u in space and time? We will show that, surprisingly, the consequences of some word can have a non-linear shape.

We will also give a complete characterization of possible slope of linear shapes obtained as consequences of some word.
Finally, if time permits, we will discuss some implications of our work concerning the long term typical behavior of cellular automata through the notion of mu-limit-set



Author: Guido Lagos

Title: Comparando medidas de riesgo en una aplicacion minera



Author: Vicente Acuna

Title: On the computational complexity of enumerating all the solutions of some biological problems in metabolic networks

Abstract: In this work, we present some algorithms and complexity results for two enumeration problems that arise in the analysis of a metabolic network: the search for minimal precursors sets of a given target and the search for elementary modes of a network.

The search for precursor sets is motivated by discovering which external metabolites are sufficient to allow the production of a given set of target metabolites.

We give a simple characterisation of precursors sets by the existence of hyperpaths between the solutions and the target.
If we consider the enumeration of all the minimal precursor sets of a given target, we find that this problem cannot be solved in polynomial total time unless P=NP. Despite this result, we present two algorithms that have good performance for medium-size networks.

Elementary modes is a common tool in the study of the cellular characteristic of a metabolic network.
An elementary mode can be seen as a minimal set of reactions that can work in steady state independently of the rest of the network.

We show that enumerating all reactions containing one given reaction cannot be done in polynomial total time unless P=NP. This result provides some idea about the complexity of enumerating all the elementary modes, which corresponds to a particular case of the enumeration of vertices of a bounded polyhedron



Author: Travis Gagie

Title: Bounds from a Card Trick

Abstract: We will examine the mathematics behind variants of a card trick.

The insights we gain will lead to new lower bounds for data compression and estimating the entropy of a Markov source



Author: Emerson Melo (Caltech)



Author: Jaime Miranda

Title: Support Vector Machines and Column Generation



Author: Jeremy Barbay

Title: From Searching and Sorting to Edge Clique Covering, fast algorithms which yield fast, small, compressed data structures

Abstract: The talk will have two parts: 1. In the first part, more formal I will show some known results about the relation between time and space, such as – between searching in an ordered space and encoding integers, and – between sorting permutations and compressing them.

2. In the second part, more informal, I will hilight the search for the same kind of relationship between some Parameterized Complexity results and the compression of graphs, such as – Edge Clique Cover – Cluster Partitioning.
This is a work in collaboration with Serge Gaspers



Author: Jörg Lehnert

Title: Coloured graphs, quasi-automorphisms, and complexity of the word problem



Author: Daniel Espinoza

Title: From branching to cutting



Author: Diego Moran

Title: Maximal S-free convex sets

Abstract: Sea S un subconjunto de vectores enteros.

Un conjunto S-free convex es un conjunto convexo que no contiene puntos de S en su interior.
Un conjunto ’maximal S-free convex’ es un conjunto ’S-free convex’ que no está contenido estrictamente en ningún otro conjunto ’S-free convex’. En esta charla probamos que los conjuntos ’maximal S-free convex’ son poliedros, cuando S son exactamente todos los puntos enteros contenidos en un conjunto convexo arbitrario.
Este resultado generaliza un resultado de Basu et al. para el caso en que S son exactamente los puntos enteros contenidos en un poliedro racional y un resultado de Lovász y Basu para el caso en que S son todos los vectores de coordenadas enteras



Author: Omar Larre

Title: Equilibrio en flujos dinamicos



Author: Cristobal Guzman


El precio de la anarquía para el remate a segundo precio generalizado



Author: Martin Matamala

Title: Coloraciones de aristas inducidas por numeraciones de los vértices


La idea es asignar números enteros positivos a los vértices de un grafo de modo que al colorear una arista con el valor absoluto de la diferencia de los valores asignados a sus extremos, se obtenga una coloración propia: en cada vértice, las aristas que en él inciden tienen colores distintos.
Queremos estudiar la cantidad de números usadas en los vértices y el máximo de los números usados


Author: Eduardo Moreno

Title: Algunos problemas en Open-pit mining

Abstract: Este problema es basicamente un multi-period precedence-constrained knapsack problem, donde la dificultad principal es resolver problemas de gran tamaño (millones de nodos). En la charla discutiré la modelación (IP) del problema y la forma actual usada en los softwares comerciales para resolverlo, un algoritmo ad-hoc desarrollado para resolver la relajación lineal (LP) del problema y una heurística de redondeo del LP que nos permite tener soluciones al 5% del óptimo en instancias reales de 1 10 millones de nodos


Author: Sanjeeb Dash, IBM Watson research

Title: Complexity, and the length of cut certificates



Author: Arturo Cifuentes

Title: Problemas Algoritmicos en Finanzas



Author: Ivan Rapaport


Que (no) se puede calcular rápido cuando a una red se le agrega un nodo universal?



Author: Jose Correa

Title: Save the President