论文标题
对可回收的强大作业问题的调查
An Investigation of the Recoverable Robust Assignment Problem
论文作者
论文摘要
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）$，受到限制，即$ m_1 $和$ m_2 $至少具有共同的$ k $边缘。 我们在此问题上得出了各种结果。首先，我们表明问题是与参数$ k $相对于w [1] - hard，以及相对于可恢复性参数$ k'= n-k $。即使在高度限制的特殊情况下，这种硬度结果也会成立，即两个成本函数$ C_1 $和$ C_2 $仅将值$ 0 $和$ 1 $。 （另一方面，XP中问题的遏制很简单。）接下来，作为一个积极的结果，我们为特殊情况构建了一种多项式时间算法，其中一个成本函数是MONGE，而另一个成本函数是抗monge。最后，我们研究了匹配$ m_1 $的变体，而优化目标是计算最佳相应匹配的$ m_2 $，这是第二阶段可回收的分配问题。我们表明，此问题变体包含在随机平行复杂度类中$ \ text {rnc} _2 $，并且至少与臭名昭著的问题\ probl \ probl {精确匹配的红蓝色bipartite Graphs}，其计算复杂性是长期存在的开放问题，
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. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to the parameter $k$, and also with respect to the recoverability parameter $k'=n-k$. This hardness result holds even in the highly restricted special case where both cost functions $c_1$ and $c_2$ 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_1$ is frozen, and where the optimization goal is to compute the best corresponding matching $M_2$, the second stage recoverable assignment problem. We show that this problem variant is contained in the randomized parallel complexity class $\text{RNC}_2$, and that it is at least as hard as the infamous problem \probl{Exact Matching in Red-Blue Bipartite Graphs} whose computational complexity is a long-standing open problem
