Multi-Budgeted Matchings via the Ham Sandwich Theorem
Event details
| Date | 18.07.2014 |
| Hour | 15:15 › 16:15 |
| Speaker |
Rico Zenkluzen (ETHZ) Brief bio: Before joining ETH Zurich, Rico was a tenure-track Assistant Professor at the Johns Hopkins University, in the Department of Applied Mathematics and Statistics. Before that, he worked several years at MIT as a postdoc in the groups of Michel Goemans and Patrick Jaillet, and also shortly at EPFL, hosted by Fritz Eisenbrand. Rico holds a master's degree in Mathematics from EPFL and a PhD from the Department of Mathematics at ETH Zurich. |
| Location |
INF 211
|
| Category | Conferences - Seminars |
In many applications, one has to deal with multiple, partially conflicting constraints. In this talk, we consider a multi-objective variant of the maximum weight matching problem, which is a classical combinatorial optimization problem with numerous applications. A natural way to deal with several objectives is to turn all of the objectives but one into budget constraints. This leads to the multi-budgeted matching problem, which asks to find a maximum weight matching subject to k linear constraints with nonnegative coefficients. Whereas this problem can easily be shown to be NP hard even for k=1, I will present 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 matchings, 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*.
To prove that our algorithm is correct, we leverage two beautiful non-constructive mathematical theorems. More precisely, the Jordan Curve Theorem gives a concise and intuitive 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 correctness for any constant k.
Part of this work is joint with Fabrizio Grandoni, R. Ravi and Mohit Singh
To prove that our algorithm is correct, we leverage two beautiful non-constructive mathematical theorems. More precisely, the Jordan Curve Theorem gives a concise and intuitive 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 correctness for any constant k.
Part of this work is joint with Fabrizio Grandoni, R. Ravi and Mohit Singh
Practical information
- Informed public
- Free
Organizer
- Ola Svensson