Fetching the paper…
Reading the bibliography…
We investigate the so-called recoverable robust assignment problem on balanced bipartite graphs with $2n$ vertices, a mainstream problem in robust optimization: For two given linear cost functions $c_1$ and $c_2$ on the edges and a given integer $k$, the goal is to find two perfect matchings $M_1$ and $M_2$ that minimize the objective value $c_1(M_1)+c_2(M_2)$, subject to the constraint that $M_1$ and $M_2$ have at least $k$ edges in common.
Complexity of a 3-dimensional assignment problem
Alan M Frieze · 1983
Earlier work this paper cites.
Graph minors. II. algorithmic aspects of tree-width
Neil Robertson and Paul D. Seymour · 1986
Earlier work this paper cites.
Matching is as easy as matrix inversion
Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani · 1987
Earlier work this paper cites.
A tourist guide through treewidth
Hans L. Bodlaender · 1993
Earlier work this paper cites.
Computational complexity
Christos H. Papadimitriou · 1994
Earlier work this paper cites.
A linear-time algorithm for finding tree-decompositions of small treewidth
Hans L. Bodlaender · 1996
Earlier work this paper cites.
Perspectives of Monge properties in optimization
Rainer E. Burkard, Bettina Klinz, and Rüdiger Rudolf · 1996
Earlier work this paper cites.
Incremental network optimization: Theory and algorithms
Onur Şeref, Ravindra K. Ahuja, and James B. Orlin · 2009
Cited alongside, same era.
Assignment Problems: Revised Reprint
Rainer Burkard, Mauro Dell’Amico, and Silvano Martello · 2012
Cited alongside, same era.
Recoverable robust shortest path problems
Christina Büsing · 2012
Cited alongside, same era.
Planarizing gadgets for perfect matching do not exist
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf · 2012
Cited alongside, same era.
Parameterized algorithms, 2015
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh · 2015
Cited alongside, same era.
Recoverable robust spanning tree problem under interval uncertainty representations
Mikita Hradovich, Adam Kasperski, and Paweł Zieliński · 2017
Cited alongside, same era.
The recoverable robust spanning tree problem with interval costs is polynomially solvable
Mikita Hradovich, Adam Kasperski, and Paweł Zieliński · 2017
Later among the works it cites.
Robust recoverable and two-stage selection problems
Adam Kasperski and Paweł Zieliński · 2017
Later among the works it cites.
Efficient algorithms for the recoverable (robust) selection problem
Thomas Lachmann and Stefan Lendl · 2019
Later among the works it cites.
Matroid bases with cardinality constraints on the intersection
Stefan Lendl, Britta Peis, and Veerle Timmermans · 2019
Later among the works it cites.
http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs
Exact matching in red-blue bipartite graphs · 2020
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Yuni Iwamas and Kenjiro Takayawa · 2020
Closest in time.