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

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

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


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.

Share:Facebook|Twitter|LinkedIn|

 

    Rico Zenklusen