Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > Multi-Budgeted Matchings via the Ham Sandwich Theorem
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



Multi-Budgeted Matchings via the Ham Sandwich Theorem

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


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.



    Rico Zenklusen