Seminarios 2011

2011-12-21:

Author:

Diana Piguet, University of Birmingham

Where:

Sala 33 DII, 14:15-15:15

Title:

Embedding cycles of given length in oriented graphs

Abstract:

Kelly, Kühn and Osthus conjectured that for any ℓ ≥ 4 and the smallest number k ≥ 3 that does not divide ℓ, any large enough oriented graph G with δ+(G),δ-(G) ≥ ⌊|V (G)|∕k⌋ + 1 contains a directed cycle of length ℓ. We prove this conjecture asymptotically for the case when ℓ is large enough compared to k and k ≥ 4. This is joint work with Daniela Kühn and Deryk Osthus.

 

2011-12-14:

Author:

Luis Briceno

Where:

Sala 33 DII, 14:15-15:15

Title:

Algoritmos de separación para resolver inclusiones monótonas: Aplicaciones y preguntas abiertas

Abstract:

En la literatura existen dos algoritmos clásicos para encontrar un cero de la suma de dos operadores maximalmente monótonos cuando uno de ellos es unívoco. El algoritmo explícito-implícito permite resolver este problema cuando la inversa del operador unívoco es fuertemente monótona. En el caso que el operador unívoco sea solamente Lipschitz, el algoritmo explícto-implícito-explicito resuelve el problema agregando un paso explícito al algoritmo anterior. Como la propiedad de inversa fuertemente monótona es mas fuerte que la propiedad Lipschitz, una pregunta abierta es saber si el primer método es más eficiente numericamente que el segundo cuando la propiedad de inversa fuertemente monótona es satisfecha. El caso particular de problemas de optimización convexa es estudiado y aplicaciones a juegos no cooperativos y a inclusiones monotónas en dualidad son desarrolladas.

 

2011-12-07:

Author:

Alejandro Hevia

Where:

Sala de Seminarios *4to* piso DCC, 14:15-15:15hrs.

Title:

Short Transitive Signatures For Directed Trees

Abstract:

A transitive signature scheme allows us to sign a graph in such a way that, given signatures on edges (a,b) and (b,c), it is possible to compute the signature on edge (a,c) without the signer’s secret. Constructions for undirected graphs are known but the case of directed graphs remains open. A first solution for the particular case of directed trees (DTTS) was given by Yi at CT-RSA 2007. In Yi’s construction, the signature for an edge is (nlog(nlog(n))) bits long in the worst case where n is the number of nodes. A year later in Theoretical Computer Science 396, Neven proposed a simpler scheme where the signature size is reduced to (nlog(n)) bits. Although this construction is more efficient, (nlog(n))-bit long signatures still remain impractical for large n. In this work, we propose a new DTTS scheme such that, for any value L ≥ 1 and security parameter k:

  • edge signatures are only (k * L) bits long,
  • signing or verifying an edge signature requires (L) cryptographic operations, and
  • computing (without the secret key) an edge signature in the transitive closure of the tree requires (Ln1∕L) cryptographic operations.

To the best of our knowledge this is the first construction with such a trade off. Our construction relies on ”hashing with common-prefix proofs”, a new variant of collision resistance hashing. A family F provides hashing with common-prefix proofs if for any H in F, given two strings X and Y equal up to position i, a prover can convince anyone that X[1…i] is a prefix of Y by sending only H(X),H(Y ), and a small proof. We believe that this new primitive will lead to other interesting applications. (This is joint work with Philippe Camacho, to appear in CT-RSA 2012).

 

2011-11-30:

Author:

Charles Thraves

Title:

On the Equilibrium of preannounced pricing policies with strategic consumers.

Abstract:

Determining an optimal pricing policy when selling to strategic consumers is a growing research area. Previous research has investigated the expected performance of different pricing and allocation schemes. Most of the implied results rely on the notion of an equilibrium between the seller and the buyers, and within the buyers themselves. Despite the growing attention of this research area, most of the studies do not analyze the equilibrium properties of such solutions. In this paper, we analyze the equilibrium properties when designing a pricing policy for a good with finite inventory and strategic consumers. We show existence of equilibrium and uniqueness when only one unit is on sale. If however multiple units are to be sold, we show that a multiple equilibria may arise, and therefore the sellers capability of optimizing its pricing policy is rather limited

 

2011-11-16:

Author:

Maurice Queyranne

Title:

Carathéodory, Helly and Radon Numbers for Sublattice Convexities

Abstract:

The Carathéodory, Helly, and Radon numbers are three main invariants in convexity theory.
They have been determined, exactly or approximately, for a number of different convexity structures.
We present new results on the exact Carathéodory numbers for the convexities defined by sublattices of d-dimensional Euclidian, integer and Boolean vector spaces.
Our results imply, for example, that if a subset S of a d-element set D can be obtained with unions and intersections from a given family G of subsets of D, then S can be obtained with unions and intersections from a small subfamily of G.
We also consider convexities induced by polyhedra defined by dual (generalized) network flow constraint systems.
We determine the Helly and Radon numbers of such convexities, and very close upper and lower bounds for their Carathéodory numbers.
In particular, for the L-natural convexities this number is the optimum value of a problem in extremal combinatorics, namely, the maximum size of a minimal cover of all pairs of elements from a (d + 1)-element set with permutations of that set.
This is joint work with Fabio Tardella (Facoltà di Economia, Sapienza Università di Roma)

 

2011-11-09:

Author:

Salvador Flores

Title:

Conexiones entre la regresión lineal con alto punto de ruptura y la adquisición comprimida de datos (Compressed Sensing)

Abstract:

La adquisición comprimida de datos consiste en recuperar un vector desconocido a partir de combinaciones lineales de sus componentes (mediciones).
Paradójicamente, es posible reconstruir exactamente un vector a partir de un número de mediciones que puede ser muy inferior al número de componentes del vector.
La estimación del nivel de sub-muestreo que permite reconstrucción exacta de una señal en la práctica se efectúa mediante la llamada propiedad de isometría restringida de la matriz de codage.
Verificar si una matriz dada posee la propiedad de isometría restringida es un problema combinatorial complejo.
Por otro lado, la regresión lineal robusta con alto punto de ruptura consiste en obtener estimadores de regresión lineal consistentes a partir de datos contaminados con errores de estructura y magnitud arbitraria.
El nivel de robustez de un estimador es cuantificado mediante el llamado punto de ruptura.
El punto de ruptura de un estimador posee una caracterización de carácter combinatorial.
En esta charla, luego de dar una descripción de ambos problemas, mostraremos que en el caso particular del estimador L1 se trata de problemas equivalentes, y que las caracterizaciones existentes para el punto de ruptura de dicho estimador proveen al mismo tiempo una caracterización del nivel de sub-muestreo admisible para reconstrucción exacta.
Esta caracterización es una mejora con respecto a la propiedad de isometría restringida, que es solo una condición suficiente

 

2011-11-02:

Author:

Flavio Guinez

Title:

The k-partition problem for submodular functions

Abstract:

En esta charla hablaremos sobre el k-partition problem para funciones submodulares, esto es, dada una función f en los subconjuntos de V, encontrar una partición {P1,…,Pk} de V que minimice el costo f(P1) + … +f(Pk).
Este problema tiene aplicaciones tanto en el área de clustering como en el diseños de circuitos VLSI.
Revisaremos algunos de los principales resultados del área, con especial énfasis a un reciente approach de Xiao para resolver el caso k=3, junto con una posible extensión para el caso k=4

 

2011-10-26:

Author:

Roberto Cominetti

Title:

Calculo de Envolventes Convexas y de Equilibrios de Nash: Algoritmos de relajacion via programacion semi-definida

Abstract:

En esta charla les contare un enfoque novedoso de Laraki-Lasserre para calcular equilibrios en estrategias mixtas para juegos finitos con n jugadores, asi como otros juegos con pagos polinomiales y/o funciones racionales.
La tecnica utiliza relajaciones de tipo SDP (Semi-Definite Programming) y se basa en un resultado reciente de Putinar’1993 en geometria algebraica

 

2011-10-12:

Author:

Jeremy Barbay

Title:

Splay Trees [1985, Sleator and Tarjan]

Abstract:

A splay tree is a self-adjusting binary search tree invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985, designed so that recently accessed elements are quick to access again.
It supports basic operations such as insertion, look-up and removal of an element x via one basic operation, Splaying the tree for x, which rearranges the tree via rotations so that x is placed at the root of the tree.
Placing the last item accessed at the top of the tree yields several interesting properties on the complexity of a sequence S of queries:

  • if x was last accessed d accesses before, searching for x costs (lg d); in particular if S is restricted to w of the n elements of T (i.e. small working set), the amortized cost of each search is (lg w) if S is sufficiently large;
  • if the last accessed element is separated from x by g elements, searching for x costs (lg g); in particularw if the elements of S are consecutive in T (i.e. g = 1), the amortized cost of S is (|S| + lg n);
  • yet the amortized complexity of each search is (lg n).

Many classical algorithms (e.g. insertion sort (n2)) can be improved by replacing a classical ordered data-structure (e.g. sorted sub-array) by a splay tree and taking advantage of (some of) those properties.
I will review the basics on Binary Search Trees and amortized analysis (skipping of you know it), the definition of splay trees and its properties, hilight two simple applications (sorting and optimal boxes) and state Sleator and Tarjan’s conjecture (along with Tango Trees, Demaine et al.’s try at it)

 

2011-10-05:

Author:

Jose Soto:

Title:

Conjuntos estables (o independientes) de rectángulos en el plano

Abstract:

Siempre he tenido problemas por lo ambiguo que son los términos estable o independiente ya que son muy usados en probabilidades, sistemas dinámicos, etc.
En este caso uso su acepción habitual de teoría de grafos, donde considero el grafo de intersección de una familia de rectángulos dada.
En otras palabras, los problemas de los cuales voy a hablar son del tipo: dado una familia de rectángulos (con pesos) en el plano, encontrar una subfamilia de rectángulos disjuntos par a par que tenga peso máximo

 

2011-09-28:

Author:

Barbay, Navarro, Perez-Lantero

Title:

Adaptive Algorithm for Optimal Planar Boxes

Abstract:

Given a set P of n planar points, two axes and a real-valued monotone decomposable score function f() on subsets of P, the Optimal Box consists in finding a box (i.e. axis-aligned rectangle) H maximizing f(H ∩ P).
We describe a fully dynamic MCS-tree [Cortés et al., J.Alg. 2009] data structure supporting insertions and deletions with the dynamic finger property, which yields a solution for the Optimal Box performing (n2 lgn) function computations and coordinate comparisons in the worst case, and much less in easier cases, taking advantage of the sign distribution of the scores and of the relative positions of the points

 

2011-09-21:

Author:

Gonzao Navarro, Yakov Nekrich

Title:

Top-k Document Retrieval in Optimal Time and Linear Space

 

2011-09-14:

Author:

Ivan rapaport

Title:

Redes de interconexión: Sincronía y Asincronía

 

2011-09-07:

Author:

Tito de Melo

Title:

Optimization with Risk via Stochastic Dominance Constraints

Abstract:

The theory of stochastic dominance provides tools to compare the distributions of two random variables.
Notions of stochastic dominance have been used in a wide range of areas, from epidemiology to economics, as they allow for comparison of risks.
Such concepts are also useful in an optimization setting, where they can be used as constraints to control for risk an area that has gained attention in the literature since its introduction by Dentcheva and Ruszczynski in a 2003 paper.
The use of stochastic dominance in a multivariate setting can then allow for multi-criterion risk comparisons, which is useful not only for optimization but also from a pure decision-making perspective.
The multivariate setting, however, poses significant challenges, as even testing for such conditions may be difficult.
In this talk we introduce some alternative concepts based on the notion of multivariate linear dominance, where linear combinations of the underlying random vectors are compared using coefficients from a certain user-specified set that may represent the opinions of multiple decision makers.
When the random vectors being compared have discrete distributions, these new stochastic dominance relationships can be represented by a finite number on inequalities.
Moreover, some of these concepts can be parameterized in order to allow for a relaxation of the dominance condition.
These results yield concrete conditions can be checked, either as stand-alone comparisons or as constraints in the optimization setting.
We discuss these formulations in detail and present some practical examples to illustrate the ideas.
(Joint work with Jian Hu and Sanjay Mehrotra from Northwestern University)

 

2011-08-31:

Author:

Enzo di Suma

Title:

A three-level MILP model for generation and transmission expansion planning

 

2011-08-17:

Author:

Martin Loeb

 

2011-08-10:

Author: Jose Correa

Title:cApproximation algorithms for graphic TSP

Abstract: Veremos nuevos resultados de Momke & Svensson (FOCS 2011) y de Oveis Gharan, Saberi, & Singh (FOCS 2011) que entregan mejoras al algoritmo de Christofides para aproximar TSP cuando la metrica es grafica.

En particular estudiaremos el problema en grafos cubicos, demostrando que en todo grafo cubico 2 conexo existe un paseo euleriano de largo 4/3 n, donde n es el numero de vertices. Luego veremos la conexion entre el problema en grafos cubicos y el caso general

 

2011-08-03:

Author: Jérémy Barbay, Jorge Romo, Hernan Fierro

Title: Boot Strapping Databases: TripDroid and Repositorium

Abstract: Calibrated Peer Reviewing (CPR) coordinates the evaluation of the quality content of a database by a collection of agents (people or programs) in the presence of a minority of malevolent agents.

Whereas existing databases using CPR have external incentives for users to contribute both documents and evaluation, in a Boot Strapping Data Base (BSDB) users must contribute new data and evaluation of submited data in order to get access to the best content of the database.

We implemented the concept of BSDB in two projects.

The project Repositorium manages databases of textual documents (e.g. multichoice questions, exam problems, marking schemes and solutions), whereas the project TripDroid manages a database of geographic informations accessed through smartphones.
The beta version of both projects will be evaluated in the next semester.

The objective of this talk is to describe the quality control features of both project, and to collect feedback on the possibility to model them mathematically, in particular in order to reduce the dimension of their parametrization (e.g. 4 constants of linear function rewarding or punishing good and bad behaviors) to a single parameter (e.g. proportion of bandwith occupied by malevolent agents), while keeping desired properties of the BSDB (e.g. volume growth, quality increase, reduced cost of quality control)

 

2011-06-22:

Author: Cristobal Guzman

Title: Un nuevo modelo para restauración de imágenes

Abstract: El primer modelo de restauración de imágenes a través de la variación total fue propuesto en 1992 por Rudin, Osher y Fatemi.

Este modelo tiene la particularidad de penalizar apropiadamente las discontinuidades de tonalidad en una imagen, a diferencia de otros estimadores, tales como mínimos cuadrados.

Lamentablemente, la complejidad de este problema crece de forma restrictiva para los métodos de optimización basados en subgradientes.

Para métodos optimales, pese a existir convergencia lineal de los iterados, la complejidad escala linealmente en el número de pixeles.

En este trabajo se propone un nuevo modelo para reconstrucción de imágenes, inspirado en la regularización por variación total.
La idea consiste en plantear el problema de optimización en el espacio de gradientes, y a través de dicho gradiente proponer una imagen consistente.

Veremos que este modelo se diferencia (en términos del conjunto factible) por un factor logarítmico del de la variación total, y cómo esta relajación reduce la dependencia de la complejidad en el número de pixeles a un factor logarítmico.
Éste es un trabajo en conjunto con Arkadi Nemirovski

 

2011-06-15:

Author: Carlos Pulgar-Juan Escobar

 

2011-06-08:

Author: Arturo Cifuentes

Title: Discounted Cash Flow (DCF) Analysis: Some Troubling Issues

 

2011-06-01:

Author: Guillermo Duran

Title: Forbidden induced subgraph characterizations of graph classes

Abstract: In this talk we present several results about partial characterizations of different graph classes by forbidden induced subgraphs.

First, we analyze three classes related to perfect graphs: clique-perfect graphs, coordinated graphs and balanced graphs.
Furthermore, we study two important classes of intersection graphs: circular-arc graphs and circle graphs.
We will show the main results on these topics obtained for our group in the last 10 years.

Joint work with F. Bonomo, M. Chudnovsky, L. Grippo, M. Groshaus, Mi.Lin, M. Safe, F. Soulignac, G. Sueiro, J. Szwarcfiter and A. Wagler

 

2011-05-25:

Author: Neil Olver (MIT) (Joint work with Navin Goyal and Bruce Shepherd)

Title: The VPN Conjecture

Abstract: Consider the problem of setting up a virtual private network (VPN) for a company, by reserving bandwidth on an existing underlying network.

This we would like to do as cheaply as possible, while ensuring we reserve enough capacity to meet the company’s needs.
A complication is that the demand pattern across the VPN – which terminals in the network are communicating with which others, and how much bandwidth they need – is not fixed, but uncertain and changing with time.

Robust network design is an approach to this difficulty; a set of possible demand patterns is specified, and we must ensure there is enough capacity to route any demand in this uncertainty set.

A particular way of specifying this uncertainty set, the hose model, has been quite intensively studied, first in the networking community and later by theoreticians.
The VPN Conjecture stated that the optimal capacity reservation in the network under this model always takes the form of a tree.

I will discuss the resolution of this conjecture, which as a consequence shows that the problem is polytime solvable.
I will also mention some open problems

 

2011-05-18:

Author: Felipe Alvarez, Julio Lopez, Hector Ramirez

Title: INTERIOR PROXIMAL ALGORITHM WITH VARIABLE METRIC FOR SECOND-ORDER CONE PROGRAMMING: APPLICATION TO SUPPORT VECTOR MACHINES

Abstract: In this work, we propose an inexact interior proximal type algorithm for solving convex second-order cone programs.

This kind of problems consists of minimizing a convex function (possibly nonsmooth) over the intersection of an ane lineal manifold with the Cartesian product of second-order cones.

The proposed algorithm uses a distance variable metric, which is induced by a class of positive denite matrices, and an appropriate choice of regularization parameter.

This choice ensures the well-denedness of the proximal algorithm and forces the iterates to belong to the interior of the feasible set.
Also, under suitable assumptions, it is proven that each limit point of the sequence generated by the algorithm solves the problem.
To show how our algorithm works in practice, computational results applied to support vector machines is presented.
Finally, we described the Bundle method with distance variable metric for solving this kind of problems with objective function nonsmooth and report several numerical tests

 

2011-05-11:

Author: Jorge Vera

Title: Geometría en Optimización lineal cónica: impactos en complejidad y robustez

Abstract: En esta charla mostraré una de mis líneas de investigación que se ha concentrado en estudiar la forma en que ciertas características geométricas de un problema de optimización cónica pueden influir en aspectos importantes como la complejidad de algunos algoritmos y también la sensibilidad y robustez de las soluciones que se puedan calcular a esos problemas.

Explicare brevemente algunos resultados conectados con la complejidad del Algoritmo Elipsoidal cuando se aplica a estos problemas para después discutir algunos resultados recientes que se conectan con sensibilidad y robustez de soluciones, márgenes tolerables de perturbación para un problema, así como cotas al tamaño de soluciones duales.
También plantearé algunas preguntas abiertas y potenciales implicancias

 

2011-05-04:

Author: Tjark Vredeveld (U. Maastricht)

Title: Smoothed performance guarantees of local search and the price of anarchy

Abstract: In this talk I consider the concept of smoothed performance guarantees and apply it to the quality of local optima.

Smoothed analysis was introduced by Spielman and Teng (JACM 2004) as a hybrid between worst case and average case analysis, to explain the good behavior of algorithms that have a bad worst case performance.

Up to now, smoothed analysis has been mainly applied to the running time of algorithms.
We will use smoothed analysis to investigate the approximation ratio of an algorithm, that is, the ratio between the value of an approximate solution and the optimal solution value.

In the last decade, there has been a strong interest in understanding the worst case behavior of local optimal solutions.
We extend this research by investigating whether or not this worst case behavior is robust.
We will apply the concept of smoothed performance guarantees to several local optima for some scheduling problems.
Joint work with: Cyriel Rutten (Maastricht University), Tobias Brunsch and Heiko Röglin (University of Bonn)

 

2011-04-27:

Author: Bernardo Pagnoncelli

Title: El problema de la cosecha óptima bajo incertidumbre de precios

 

2011-04-20:

Author: Nicolas Figueroa

Title: Robustez y Diseno de Mecanismos

 

2011-04-13:

Author: Pablo Pérez Lantero

Title: Locating a service facility and a rapid transit line

Abstract: We study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total (or maximum) travel time from the clients to the facility, using the L1 or Manhattan metric.

The rapid transit line is given by a segment with any orientation, and represents an alternative transportation line that can be used by the clients to reduce their travel time to the facility.

We consider some variants of the problem according to the highway’s length and the way in which the clients enter and exit the highway

 

2011-04-06:

Author: Juan Peypouquet

Title: Algoritmos de penalización para problemas de optimización con restricciones

 

2011-03-30:

Author: Pablo Barcelo

Title: Parameterized Regular Expressions and Their Languages

Abstract: We study regular expressions that use variables, or parameters, which are interpreted as alphabet letters.

We consider two classes of languages denoted by such expressions: under the possibility semantics, a word belongs to the language if it is denoted by some regular expression obtained by replacing variables with letters; under the certainly semantics, the word must be denoted by every such expression.

Such languages are regular, and we show that they naturally arise in several applications such as querying graph databases and program analysis.

As the main contribution of the paper, we provide a complete characterization of the complexity of the main computational problems related to such languages: nonemptiness, universality, containment, membership, as well as the problem of constructing NFAs capturing such languages.

We also look at the extension when domains of variables could be arbitrary regular languages, and show that under the certainty semantics, languages remain regular and the complexity of the main computational problems does not change

 

2011-03-22:

Author: Speaker: Shabir Ahmed (GaTech)

Title: Risk Averse and Distribution Robust Stochastic Programming

Abstract: Two typical criticisms for the classical stochastic programming paradigm are that it is risk neutral and requires precise distributional information.

In this talk we discuss extensions of the stochastic programming paradigm that attempt to alleviate these issues.
In particular, we address stochastic programming models involving a class of coherent risk objectives and those involving value-at-risk criteria.

Our treatment is primarily from an algorithmic viewpoint.
Specifically, we extend the theory of sample average approximation (SAA) method and develop specialized optimization algorithms for these classes of stochastic programs

 

2011-03-16:

Author: Fabian Hundertmark (Hamburgo)

Title: Canonical tree-decompositions and nested separation systems of nite graphs

Abstract: We provide a method to construct tree-decompositions of a graph that separate highly connected parts from each other and which are canonical in the sense that their construction only depends on properties of a graph that stay invariant under automorphisms of that graph.

To achieve this goal we develop a method to select a canonical nested subsystem of a given separation system, that preserves certain separation- properties.

Our method is very lightweight in the sense that it easily adapts to different notions of highly connected parts.
In that way we are able to prove major improvements of previous results by Robertson and Seymour and by Dunwoody and Krön