License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.19
URN: urn:nbn:de:0030-drops-154025
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15402/
Fischer, Dennis ;
Hartmann, Tim A. ;
Lendl, Stefan ;
Woeginger, Gerhard J.
An Investigation of the Recoverable Robust Assignment Problem
Abstract
We investigate the so-called 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/2-k. 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 Anti-Monge. 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 Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing 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:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-216-7},
ISSN = {1868-8969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15402},
URN = {urn:nbn:de:0030-drops-154025},
doi = {10.4230/LIPIcs.IPEC.2021.19},
annote = {Keywords: assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC}
}
|
Keywords: |
|
assignment problem, matchings, exact matching, robust optimization, fixed paramter tractablity, RNC |
|
Collection: |
|
16th International Symposium on Parameterized and Exact Computation (IPEC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
22.11.2021 |
