Error message

  • Deprecated function: Optional parameter $js declared before required parameter $element is implicitly treated as a required parameter in include_once() (line 1445 of /var/www/html/mathtube.org/includes/bootstrap.inc).
  • Deprecated function: Optional parameter $input declared before required parameter $form_state is implicitly treated as a required parameter in include_once() (line 1445 of /var/www/html/mathtube.org/includes/bootstrap.inc).

Invariant Matching

Speaker: Alexander Holroyd

Date: Fri, Jun 22, 2012

Location: PIMS, University of British Columbia

Conference: PIMS-MPrime Summer School in Probability

Subject: Mathematics, Probability

Class: Scientific

Abstract:

Suppose that red and blue points occur as independent point processes in Rd, and consider translation-invariant schemes for perfectly matching the red points to the blue points. (Translation-invariance can be interpreted as meaning that the matching is constructed in a way that does not favour one spatial location over another). What is best possible cost of such a matching, measured in terms of the edge lengths? What happens if we insist that the matching is non-randomized, or if we forbid edge crossings, or if the points act as selfish agents? I will review recent progress and open problems on this topic, as well as on the related topic of fair allocation. In particular I will address some surprising new discoveries on multi-colour matching and multi-edge matching.