Fischer, Dennis ;
Hartmann, Tim A. ;
Lendl, Stefan ;
Woeginger, Gerhard J.
An Investigation of the Recoverable Robust Assignment Problem
Abstract
We investigate the socalled recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ have at least k edges in common.
We derive a variety of results on this problem. First, we show that the problem is W[1]hard with respect to parameter k, and also with respect to the complementary parameter k' = n/2k. This hardness result holds even in the highly restricted special case where both cost functions c₁ and c₂ only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is AntiMonge. Finally, we study the variant where matching M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², and we show that it is at least as hard as the infamous problem Exact RedBlue Matching in Bipartite Graphs whose computational complexity is a longstanding open problem.
BibTeX  Entry
@InProceedings{fischer_et_al:LIPIcs.IPEC.2021.19,
author = {Fischer, Dennis and Hartmann, Tim A. and Lendl, Stefan and Woeginger, Gerhard J.},
title = {{An Investigation of the Recoverable Robust Assignment Problem}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {19:119:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15402},
URN = {urn:nbn:de:0030drops154025},
doi = {10.4230/LIPIcs.IPEC.2021.19},
annote = {Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
22.11.2021
Keywords: 

assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC 
Seminar: 

16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Issue date: 

2021 
Date of publication: 

22.11.2021 