Seminarios 2009

2009-12-09:

Author: Omar Larre

Title: Sobre el problema de reventar globos y sus aplicaciones a subastas

Abstract: Mostramos resultados sobre el retorno de una subasta online donde se ofrecen items idénticos a compradores anónimos que demandan solo una unidad.

En este contexto, incluso bajo el conocimiento previo de la distribucion exacta de las valoraciones de los compradores, ninguna subasta puede extraer en valor esperado más que una constante por el beneficio de una subasta a precio fijo.
El valor más recientemente conocido de esta constante es 2. eSte problema es equivalente al problema de diseñar una estrategia óptima para inflar globos con capacidades conocidas, con el fin de maximizar la cantidad de aire contenido

 

2009-12-02:

Author:

Jeremy Barbay

Title:

From Output Sensitivity to Instance Optimality

Abstract:

From sorting to many NP-hard problems, the pessimism of worst case analysis is progressively replaced with finer approaches, such as /output sensitivity/, /adaptive analysis/, /parameterized complexity/, /competitive analysis/, /smooth analysis/, /instance optimality/. In the same way that compression schemes take advantage of the specificities of data (e.g. image, music, video) in order to compress it better, practical algorithms take advantage of the specificities of an instance to solve it faster (than the worst case over instances of comparable size). Using this concept to revisit previously known algorithms, one sometimes discovers that they perform better than was previously thought.
In this talk I will describe the basis of this approach, and as an illustration, a sequence of results on the computation of the planar convex hull from the first approach to the latest, instance optimal results.
This work is in collaboration with Peyman Afshani and Timothy Chan

2009-11-25:

Author:

Arash Farzan, PhD Universidad de Waterloo, Canadá

Title:

Towards Unifying Succinct Representations of Trees

Abstract:

A succinct representation of a combinatorial object is a highly space-efficient representation on the RAM with logarithmic word size that supports dynamic queries in constant time.
In this talk, we mainly focus on succinct representation of trees which have found an increasing number of applications in indexing massive collections of textual and semi-structured data.
In the first part of the talk, we sketch a uniform approach in succinct representation of trees which enhances the power of pre- existing succinct representations of trees for various families of trees (such as ordered andk-ary trees). In the second part of the talk, we focus on ordered trees and present a universal representation with the feature that it can simultaneously emulate most of the prominent pre-existing succinct representations of ordered trees.
Hence, the universal representation unifies these representations and combines their power

2009-11-18:

Author:

Nicolas Figueroa

Title:

Subastas Óptimas

2009-11-04:

Author:

Serge Gaspers

Title:

parametrized complexity

2009-10-28:

Author:

Ron Adany, Bar Ilan University

Title:

Personal Advertisement Allocation for Mobile TV

Abstract:

. abstract: Personal advertisements are the next-generation in the world of advertisement.
In this article we consider the personal advertisement allocation problem with constraints that are motivated by the TV and Mobile advertisement worlds.
This problem is a version of the Generalized Multi-Assignment Problem, defined as an extension of GAP with assignment restrictions and all-or-nothing constraints.
We present an Integer Programming (IP) model of the problem, prove that it is an NP-hard problem, and propose heuristic algorithms to solve it. Through computational experiments, we compare the performance of these heuristics to solutions obtained with IP solvers

2009-10-21:

Author:

Serge Gaspers

Title:

Parametrized Complexity

2009-08-05:

Author:

Roberto Cominetti

Title:

seleccion optima de clientes en promociones de ultimo minuto

2009-06-15:

Author:

Nicolas Stier

2009-06-08:

Author:

Flavio Guinez

2009-06-01:

Author:

Fernando Ordonez

Title:

warm start metodos for interior point algorithms

2009-05-25:

Author:

Marcela Munizaga 15:00 Ing. Civil (laboratorio transportes)

2009-05-18:

Author:

Jose Correa

Title:

Scheduling Games

Abstract:

15:00 DII, sala por confirmar

2009-05-11:

Author:

Miguel Constantino

Title:

Node Weighted Connected Subgraph

Abstract:

We consider the following problem: given a graph G = (V,E) and node weights, find a set of nodes U such that the subgraph induced by U is connected and has maximum weight.
This problem is NP-hard in general and polynomialy solvable for series parallel graphs.
In this talk we review IP models and polyhedral results and point out some open issues

2009-04-27:

Author:

Maurice Queyranne

Title:

Algebraic methods for Integer Programming

2009-04-20:

Author:

Daniel Espinoza

Title:

Maximal Convex Latice Free Sets and Cutting planes

2009-04-13:

Author:

Nicolas Figueroa

2009-03-30:

Author:

Richard Walts

Title:

New Active-Set Methods for Nonlinear Programming: Moving Beyond SQP

2009-03-23:

Author:

Jeremy Barbay

Title:

input order adaptivity: results and open problems

2009-03-16:

Author:

Maurice Queyranne

Title:

Barvinok generating functions for integer programs and integer programming games