Bi-Weekly Talk: Dennis Fischer
Wednesday, August 07, 2019, 10:30am
Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10
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-hard even on planar graphs and present a polynomial time algorithm for the special case where c_1 is monge and c_2 antimonge.