BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Multi-Budgeted Matchings via the Ham Sandwich Theorem
DTSTART:20140718T151500
DTEND:20140718T161500
DTSTAMP:20260503T140624Z
UID:8aa46434e3417ae3d55ebef81def353da036c15c7d70465b52960fef
CATEGORIES:Conferences - Seminars
DESCRIPTION:Rico Zenkluzen (ETHZ)\nBrief bio: Before joining ETH Zurich\,
  Rico was a tenure-track Assistant Professor at the Johns Hopkins Universi
 ty\, in the Department of Applied Mathematics and Statistics. Before that\
 , he worked several years at MIT as a postdoc in the groups of Michel Goem
 ans and Patrick Jaillet\, and also shortly at EPFL\, hosted by Fritz Eisen
 brand. Rico holds a master's degree in Mathematics from EPFL and a PhD fro
 m the Department of Mathematics at ETH Zurich.\nIn many applications\, one
  has to deal with multiple\, partially conflicting constraints. In this ta
 lk\, we consider a multi-objective variant of the maximum weight matching 
 problem\, which is a classical combinatorial optimization problem with num
 erous applications. A natural way to deal with several objectives is to tu
 rn all of the objectives but one into budget constraints. This leads to th
 e multi-budgeted matching problem\, which asks to find a maximum weight ma
 tching subject to k linear constraints with nonnegative coefficients. Wher
 eas this problem can easily be shown to be NP hard even for k=1\, I will p
 resent in this talk a polynomial-time approximation scheme that works for 
 any constant k. Our algorithm is based on rounding an optimal solution x* 
 of an LP relaxation. Starting with a convex decomposition of x* into few m
 atchings\, as guaranteed by Caratheodory's theorem\, we reduce the problem
  of rounding x* to an arguably simpler problem of successively merging two
  matchings in the convex decomposition of x*.\nTo prove that our algorithm
  is correct\, we leverage two beautiful non-constructive mathematical theo
 rems. More precisely\, the Jordan Curve Theorem gives a concise and intuit
 ive proof why our algorithm works for k=1\, and a result of Stromquist and
  Woodall that follows from the Ham Sandwich Theorem allows for showing cor
 rectness for any constant k.\nPart of this work is joint with Fabrizio Gra
 ndoni\, R. Ravi and Mohit Singh
LOCATION:INF 211
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR