Approximation Algorithms for k-Scenario Matching

Matching theory is among the most fundamental graph optimization problems. Several different variants of this problem have been introduced and studied. Maximum matching, capacitated matching, and perfect matchings are all well studied examples of problems in matching theory. Here we motivate and study a generalization of the maximum weighted matching problem, so-called k-scenario matching. In k-scenario matching we are given a graph G = (V,E), in which each edge belongs to at least one of the k subsets E_1, ...,E_k (scenarios), and each scenario is equipped with probability pi for each 1 ≤ i ≤ k. We are provided with budget, some integer B, and our goal is to find a subset ˆE ⊆ E of size at most B, that maximizes the expected value of the maximum cardinality matchings on all the possible k scenarios (i.e. Sum_{i=1}^k pi|Mi| where Mi is a maximum matching on edges E-hat ∩ E_i.) This problem is motivated by applications such as kidney exchange, where compatibility between donors and patients is uncertain. Tests must be performed to ascertain whether two vertices can be matched, but due to the time and cost involved, only a limited number of tests are possible. In this paper we show that this problem is NP-hard even in the simple case where we have two scenarios, and the input graph is both bipartite and sub-cubic. We also study the approximability of this problem in
several cases from the positive direction. For the general case of this problem, we find a 2.314-approximation by a natural greedy algorithm. We then present two approximation algorithms for the case where there are two scenarios. When p1 = p2 = 1 2 , our first algorithm achieves a 11/9-approximation. When p1 is not equal p2, we show that this problem admits a 5/4 -approximation. For the general case of this problem, we find a 2.314-approximation by a natural greedy algorithm.