The stochastic matching problem

Details The stochastic matching problem The stochastic matching problem

2011-05-18

arxiv.org/abs/1105.3657v1

Phys. Rev. Lett. 106, 190601 (2011)

Physics

Condensed Matter

Statistical Mechanics

Published version has very minor changes

Scientific paper

10.1103/PhysRevLett.106.190601

The matching problem plays a basic role in combinatorial optimization and in statistical mechanics. In its stochastic variants, optimization decisions have to be taken given only some probabilistic information about the instance. While the deterministic case can be solved in polynomial time, stochastic variants are worst-case intractable. We propose an efficient method to solve stochastic matching problems which combines some features of the survey propagation equations and of the cavity method. We test it on random bipartite graphs, for which we analyze the phase diagram and compare the results with exact bounds. Our approach is shown numerically to be effective on the full range of parameters, and to outperform state-of-the-art methods. Finally we discuss how the method can be generalized to other problems of optimization under uncertainty.

Affiliated with

Also associated with

No associations

Rating

The stochastic matching problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The stochastic matching problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The stochastic matching problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54271