Wednesday 5 February 2014, 4.30pm - 6.00pm
AGRW (Graham Wallace Room), 5th Floor, Old Building
Rico Zenklusen
Institute for Operations Research, ETH Zürich
Personal Profile
Abstract:
In many applications, one has to deal with multiple, partially conflicting constraints. In this talk, we study a multi-objective variant of a classical combinatorial optimization problem, namely the maximum weight matching problem. 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.
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.