Greedy Heuristics and Stochastic Matchings

Joydeep Mukherjee, C.R. Subramanian


We analyze the performance of some greedy heuristics for the weighted version of the stochastic matching (under the {\em probe-and-commit with patience constraints} model) as introduced by Chen et al., [5].  As input a random subgraph $H$ of a given edge-weighted graph $(G=(V,E), \{w_e\}_e)$ (where each edge $e \in E$ is present in $H$ independently with probability $p_e$) is revealed (on a {\em probe-and-commit} basis meaning any edge $e$ that is probed and found to be present in $H$ should be included irrevocably in the matching). It is also required that the the number of probes involving a vertex $v$ cannot exceed a nonnegative parameter $t_v$ known as $v$'s patience. All of $G$, $\{w_e\}_e$, $\{p_e\}_e$ and $\{t_u\}_u$ is revealed to the algorithm before its execution. The performance of the algorithm is measured by the expected weight of the matching it produces. For approximation measures, it is compared with the expected weight of an optimal adaptive algorithm for the input instance.

We analyze a natural greedy algorithm for this problem and obtain an  upper bound of $\frac{2}{p_{min}^2}$ on the approximation factor  of its performance. Here, $p_{min}$ refers to $\min_{e \in E} p_e$. No previous analysis of any greedy algorithm for the weighted stochastic matching (under the probe-and-commit model) is known. This also improves the previously best known approximation ratio of any efficeint and adaptive algorithm when $p_{min}>\frac{1}{\sqrt{2}}$. We also establish a lower bound of $\frac{2}{p_{min}}$ on the worst-case value of the approximation ratio of the greedy algorithm.

We also analyze a class of greedy heuristics and establish that the approximation ratio of each such heuristic can become arbitrarily large even if we restrict ourselves to unweighted instances.

Full Text:



  • There are currently no refbacks.

©2019 Science Asia