Résumé
Here we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. For such problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms which, in expectation, are constant competitive, i.e., the ratio between the expected costs of the output matching and the optimal offline solution is bounded by a constant. The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. The second algorithm builds on the tools used to analyze the first one in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach cannot achieve a competitive ratio better than O(m log 1.5+ε ) in the adversarial model, where m denotes the number of agents. Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, for the asymmetric distance case, as well as for the MPMD variant with penalties to clear pending requests.