← volver

Conferencia Andreas Wiese

13:30 horas, Sala Consejo Beauchef Poniente, Beauchef 851

Andreas Wiese, Matemático de la Universidad de Durham, Inglaterra, y diplomado y doctorado en esta misma disciplina en la Technische Universität (TU) de Berlín. Profesor visitante de Ingeniería Industrial.

Título de la conferencia: “The geometric knapsack problem and fare evasion in Transantiago”

Abstract
In the first part of this talk we will study the two-dimensional geometric knapsack problem in which we are given a set of rectangular items, each one having an associated profit, and a square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack. The problem is motivated by e.g. stock cutting and placing advertisements on a board or a website. The best-known approximation factor for the problem (even just in the cardinality case) is 2+eps. We break the barrier of 2 for the first time: we present a quasi-polynomial time (1+eps)-approximation algorithm (for quasi-polynomially bounded inputs) and a polynomial time (1.89+eps)-approximation.

The second part of this talk is about our ongoing project with Transantiago, the public transportation agency in Santiago de Chile. The rate of fare evasion in Santiago is estimated to be around 30% which implies huge losses due to the unpaid fares every day. Our goal is to understand the phenomenon of evasion better (e.g., what routes evadors take etc.) and to find strategies for choosing the locations of the ticket inspectors. In particular, the latter leads to interesting game theoretical questions in which the transportation agency can be seen as one player and the fare evadors are the opponents.

Disponibilidad de refrigerio, inscripciones AQUÍ