[Seminario] INVITACION SEMINARIO AGCO 08 DE AGOSTO DEL 2018 A LAS 13:30 HRS.

[Maria Ines Rivera]

Estimados Académicos y Alumnos,

Se les invita para este miércoles 08 de agosto a las 13:30 hrs, al 
seminario  AGCO, este seminario tendrá lugar en DII, Domeyko 2338, sala 
33. *

AGCO Seminar**
**
Author**
**Ulrike Schmidt-Kraepelin**
**TU Munich.**
**
**Title**
**Maintaining Perfect Matchings **
**

Abstract: *

We investigate the minimum-cost perfect matching problem in metric 
spaces with two stages. In the first stage, an algorithm is confronted 
with a set of points from a metric space and ought to find a perfect 
matching among them. Subsequently, an adversary can announce new points 
after which the algorithm has to give a perfect matching on the extended 
set. However, for every arrived point, the algorithm can only do a 
constant number of reallocations with respect to the old matching. We 
call an algorithm for this problem (two-stage) robust if the cost of 
each matching is within a constant factor of those induced by a 
minimum-cost matching.
For general metric spaces, we can find a matching which is immune to the 
arrival of k new points, where k must be specified before the 
construction of the first matching. For the special case where the 
metric space is the real line together with the Euclidean distance, we 
present an algorithm that is robust to the arrival of any (unknown) 
number of points. Our results can be seen as a first step towards 
solving the online version of the problem.

This is joint work with José Verschae and Jannik Matuschke.

*Where: DII, Domeyko 2338, Sala 33 **
**When: Wednesday, August 8, 13:30.*


Esperando contar con su presencia, les saluda,

Ma. Inés Rivera
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listas.dim.uchile.cl/pipermail/seminario/attachments/20180806/914a3b7e/attachment.html>