The Query-commit Problem
The Query-commit Problem
复制标题
查询提交问题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Ravi
中科院分区：
文献类型：
--
作者：
M. Molinaro;R. Ravi
在查询提交问题中，我们得到一个图，其中边具有不同的存在概率。可以查询图的边，如果查询的边存在，则其端点不可撤销地匹配。目标是找到一种查询策略，使所获得的匹配的预期大小最大化。这种随机匹配设置的动机是肾脏交换和在线约会中的应用。
在本文中，我们从理论和实验的角度解决查询提交问题。首先，我们证明可以在不损害策略最优性的情况下查询一类简单的边。然后，当输入图稀疏时，使用该属性在多项式时间内获得最佳查询策略。接下来，我们将注意力转向肾脏交换应用程序，重点关注根据现有交换项目的真实数据建模的实例。我们证明，随着节点数量的增长，几乎每个实例都承认一个与几乎所有节点匹配的策略。这一结果支持了这样一种直觉，即在更大的患者/捐赠者群体中进行更多的交流是可能的，并为统一现有的交流计划提供了理论依据。最后，我们通过实验评估了肾脏交换实例的不同查询策略。我们证明，即使是非常简单的启发式方法也能表现得相当好，与预先知道图中边缘的最佳透视策略的误差在 1.5% 以内。在这样一个时间敏感的应用程序中，这个结果激发了提交策略的使用。
In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists then its endpoints are irrevocably matched. The goal is to find a querying strategy which maximizes the expected size of the matching obtained. This stochastic matching setup is motivated by applications in kidney exchanges and online dating.
In this paper we address the query-commit problem from both theoretical and experimental perspectives. First, we show that a simple class of edges can be queried without compromising the optimality of the strategy. This property is then used to obtain in polynomial time an optimal querying strategy when the input graph is sparse. Next we turn our attentions to the kidney exchange application, focusing on instances modeled over real data from existing exchange programs. We prove that, as the number of nodes grows, almost every instance admits a strategy which matches almost all nodes. This result supports the intuition that more exchanges are possible on a larger pool of patient/donors and gives theoretical justification for unifying the existing exchange programs. Finally, we evaluate experimentally different querying strategies over kidney exchange instances. We show that even very simple heuristics perform fairly well, being within 1.5% of an optimal clairvoyant strategy, that knows in advance the edges in the graph. In such a time-sensitive application, this result motivates the use of committing strategies.