【科研点子】Online Bipartite Matching with Reusable Resources中的两个Open Problem

发表于 更新于 分类于

Online Bipartite Matching with Reusable Resources这篇文献里有两个比较重要的open problem。

  1. RANKING算法在该模型下怎么分析C.R.

  2. 该模型下的最佳C.R.是多少，有可能达到吗？

就我目前的、尚未验证正确性的证明来看，这两个问题的答案是：该模型下的最佳C.R.就是，而且RANKING算法就可以达到。（更新后该结果不确定是否能得到）

首先，我们来看一下直接把[DJK13]的两个引理带进去会有什么问题，并以此作为切入点逐步解决我们的问题。

  1. Dominance Lemma仍然没有问题。然而，Monotonicity Lemma会有问题。

  2. 时，把“只在d以内有匹配”和“d以外也有匹配”的两种情形区分开，经过组合证明可发现，前者和传统情形没有区别，后者则会造成无保障的问题（也即Monotonicity Lemma不成立），其原因在于在d外有匹配可能会让的匹配被推迟，若推迟到d以内，会导致对于不可用；

  3. 解决后者的办法是，注意到尽管无保障了，但另一方面“d以外也有匹配”本身就是一件好事。也就是说，首先此时d以内必然被匹配了，另外在d以外还有一个匹配。因此，我们尝试将两个dual式并在一起考虑，以期弥补的问题。

  4. 将dual式并在一起考虑可行吗？可行。因为原来的dual式子是形如，现在合并了两个这样的式子后产生一个的式子（primal的变化类似，合并变成了一个的式子），此时我们得到了原来LP的一个relaxation，因此满足该LP，也就替代性地满足了原来的LP。

  5. 另一个问题是，通过计算可以发现，如果一个unit在间的分配方式仍然总是，那么即使采用了上面的合并方案，最后还是支撑不住C.R.。解决方法是，在“d以外也有匹配”的情形时，直接把1个unit全部给到。In retrospect，这是一种合理的想法。因为在该情形下，我们已经确信存在两个匹配，那么全部给到可以使我们完全利用到这两个确信存在的匹配。为了方便，我们后面把这种分配方案称为A方案，把传统分配方案称为B方案。（注意到，传统情形里之所以不能把unti全给，就是考虑到不总是获得匹配，因此全给在分析里就没法充分利用到。不全给同理。所以才要找一个正确的函数精细地调整该给两侧多少。这里反而不存在这种困扰了。）

  6. 还有一个问题，我们尚未交代“只在d以内有匹配”和“d以外也有匹配”如何在分析上区分开。事实上，我们可以通过组合性质证明，存在一个，当，属于“只在d以内有匹配”的情形，当时，属于“d以外也有匹配”的情形。（注意，这不代表时就不会出现上述两种情形，这只是一种有利于分析的确定性的划分。就像显然，时，也有可能被匹配，只不过时这种匹配的存在性是肯定的。）

  7. 还有一个问题，我们对unit分配方案的调整是否会产生冲突。也就是说，存不存在一条边，它可能在对自己分析的时候需要在时采用B方案，而在对后面的另一条边进行分析时，却需要在时对该边进行合并进而采取A方案。若，就会存在unit分配方案的冲突。对于这种冲突，同一采用A方案。也就是说，从自己这条边开始，可能有多个不同的会关联到这条边。取作为分界线即可。也即，当时，采用A方案。

  8. 最后一个小问题，怎么办？答案是通过简单的不等式分析和计算，会注意到C.R.会随增加而增加，则我们只需考虑的情形即可。

  9. 计算后会发现事实上时就是最差情形，也便完全退化为传统情形，而传统情形的C.R.就是。

如果上述这些环节没有问题的话，两个Open Problem就解决了！

更新：第7步开始有问题。因为如果还连到了别的上，的unit分配会被的分配策略冲突破坏掉。

再更新：保持分配策略始终不变，也足以证明。

再再更新：但好像还是会有各种奇怪的冲突。

再再再更新：能不能不管这些冲突？有没有可能证明下面这个东西：对于任意边和（表示全体种子），只要存在一种LP的relaxation形式和unit分配策略的组合，使得关于的dual条件在该组合的分析模式下是OK的，那就OK。

更形式化一点说：

我们用表示一个LP形式，用表示一个unit分配策略，将二元组称为一个分析组合。在primal-dual分析框架下，确定一个组合，我们就可以对算法开始分析。

对于任意边和，设在下的关于该边的对偶条件式为，其中为表达式，为常数。此时，对于任意，若可以证明在发生时，其中为某一常数（通常小于），我们称：

在分析组合下，边对应的对偶条件在发生时的满足率为，

记作。

记全体构成空间。

定理？：

若，则算法的竞争系数为。

（按发生概率积分）

再再再再更新：

上面这个定理不太行，可以举出反例。

感觉冲突还是不能存在（必须是前定的）。如果好好构造LP的形式应该还是至少能证明大于0.5的？留到下一个博客再写吧。