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[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.