Bi-Weekly Talk: Dennis Fischer

Mittwoch, 07.08.2019, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragender: Dennis Fischer

 

The Recoverable Robust Assignment Problem

 

Abstract: We study the following recoverable robust optimization problem: Given a bipartite graph G with real cost functions c_1 and c_2 on the edges, find perfect matchings M_1, M_2 in G that minimize c_1(M_1) + c_2(M_2) where the intersection of M_1 and M_2 contains at least k edges. We show that this problem is W[1]-hard even on planar graphs and present a polynomial time algorithm for the special case where c_1 is monge and c_2 antimonge.